RU   UA

DonNTU   Masters' portal

Dmitry Rumyantsev

Faculty of computer information technologies and automation (CITA)

Department of automation and telecommunications (AT)

Speciality Infocommunication technologies and communication systems

Investigation of traffic control mechanisms in Data Processing Centers (DPC)

Scientific adviser: Ph.D., Prof. department AT Vladimir Tyrypalov

Resume Abstract

Investigation of traffic control mechanisms in Data Processing Centers (DPC)

Содержание

• Introduction
• 1. Relevance of the topic
• 2. Purpose and objectives of the study, planned results
• 3. Overview of research and development
• 3.1 Comparative analysis of data center topologies
• 3.2 Analysis of data center traffic management methods
• 3.3 Analysis of general strategies for building an optical network with quality of service parameters
• 4. Analysis of Routing and Spectrum Assignment Approaches in Optical Data Center Networks
• 4.1 Comparative analysis of data center topologies
• 4.2 Analysis of spectrum allocation policies for routing
• Conclusion
• List of Sources

Introduction

The introduction of cloud and data-intensive applications has increased the load on global data centers (datacenters). Consequently, there is a need for high performance with the required quality of service (QoS) parameters. Special transport protocols and traffic management methods, implemented in both hardware and software of data centers, have been developed to provide them. The main components of data center networks, rack switches (ToR, Top of Rack) [1], must be connected via a large interconnect allowing machines to exchange data between racks with servers. Thus, the network described should act as a huge non-blocking switch to which all servers are directly connected, allowing the latter to exchange data simultaneously at maximum speed.

One of the well-known solutions to this problem are EON (Elastic Optic Network) or software-configurable optical networks, for which it is possible to use routing and wavelength assignment (RWA, Routing and wavelength assignment), as well as protection and recovery strategies. Let us consider the proposed solution within the framework of the research task.

1. Relevance of the topic

Modern optical switching technology makes it possible to provide high bandwidths. However, existing limitations, such as dependence on the topology used, the use of micro-electromechanical switches (MEMS), and the use of wavelength-division multiplexing (WDM) mechanism, reduce the efficiency of processing incoming traffic. Thus, the topic of the master's thesis, aimed at research and development of traffic management mechanisms in data centers is relevant.

2. Purpose and objectives of the study, planned results

The aim of the work is to improve the efficiency of elastic optical network resources of data centers with quality of service parameters by developing a method of frequency slot allocation and bandwidth reuse.

To achieve this goal, the following tasks were formulated and solved:

• analysis of the problems of effective of data center traffic management;
• аnalysis of existing mathematical models and methods of optical network spectrum allocation with quality of service parameters;
• development of a mathematical model and method for frequency interval allocation and bandwidth reuse with quality of service provision;
• evaluating the effectiveness of the developed method by simulation modeling and working out recommendations for its practical use.

The object of the study is the process of redistribution of optical resources with quality of service.

Research subject: methods of effective use of available optical network resources.

Research Methods. Methods of routing and spectrum allocation in optical networks were used to develop mathematical models and methods to improve the efficiency of the use of optical network resources. Methods of graph theory, statistical analysis were used to develop a method of spectrum allocation of optical network with quality of service; methods of mathematical modeling, mathematical programming and simulation modeling were used to analyze the proposed mathematical models.

.

The following scientific result was obtained while solving the set tasks: the method of increasing the efficiency of network resources utilization was further developed. The novelty of the method consists in improving the method of spectrum allocation of the optical network with the provision of quality of service parameters.

As part of the master's work is planned to obtain the following scientific and practical results:

1. The method of increasing the efficiency of the use of network resources has been further developed. The novelty of the method lies in the improvement of The novelty of the method is to improve the method of spectrum allocation of optical network with provision of quality of service parameters;
2. It is shown that the proposed strategy of spectrum allocation provides a decrease in the probability of network blocking by 46%, while improving performance by 22%.

3. Overview of research and development

3.1 Comparative analysis of data center topologies

• «full tree» [2]. As shown in Fig. 3.1, the topology is a multirooted tree topology in which each root is called the main switch. It can be viewed as a collapsed Klo network. By increasing the number of roots, it is possible to reduce the over-acceptance ratio (given a fixed channel capacity).
  

  Figure 3.1 — Full tree topology

  This topology provides high bandwidth using a large number of less expensive switch, which allows you to support a large number of servers at a much lower cost. The disadvantages of this topology include the use of a complex routing configuration on the switches, to avoid loops when using available paths for load balancing;;

• "leaf-barrel," Fig. 3.2, a two-level topology where the "leaves" (ToR switches) are bound to servers and each backbone switch is directly connected to all "leaf" switches, similar to a bipartite graph.
  

  Figure 3.2 — Leaf-barrel topology

  The links connected between the servers and the edge switches may have different bandwidth than the links connecting the edge switches to the backbone. The topology simplifies capacity and port expansion (by adding more trunk or leaf switches), and allows direct use of load-balanced routing without creating loops. The disadvantage of the topology is the increased cost of high-capacity trunk switches with more ports as the number of servers in the cluster increases

• virtual level 2 (VL2) [3], presented in Fig. 3.3 is characterized by the fact that it implements all routing and forwarding functions over collapsed Clo networks.
  

  Figure 3.3 — VL2 topology

  The difference between this topology and "full tree" is that the bandwidth between the switches is larger than the server-switch lines. This requires fewer physical lines between the aggregation and core layers. to connect the aggregation and core layers. Each ToR switch is connected to two aggregation switches so that each aggregation switch is connected to an equal number of edge switches;

• "jellyfish" [4], presented in Fig. 3.4, a topology in which the ports of the ToR switches are connected randomly until more channels can be added; then, for any S-switch with two or more free ports, the existing A-B channel is removed and two channels are added between the two free S and the two ends of the remote network channel (i.e. A-S and B-S) until the switch has more than one port.
  

  Figure 3.4 — Jellyfish topology

  Because ToR switches are directly connected, the average path (number of hops) is much smaller compared to three-layer collapsed Clo networks. The advantages of the topology include its scalability: at full channel load, this topology supports more servers than the "full tree" topology. In addition, with the same number of line failures, the average throughput per server in the "Medusa" topology is higher than in the "full tree" topology. The disadvantages of this topology are the low efficiency of existing routing schemes. For this topology it is assumed to use a joint streaming routing on the shortest paths with multipath TCP (MPTCP) [5].

• D-cluster, shown in Fig. 3.5 is a hierarchical data center topology [6], in which a higher-level cluster is built by combining several structures of lower-level clusters.
  

  Figure 3.5 — D-cluster topology

  The advantages of this topology include the use of a proprietary fault-tolerant routing algorithm. This allows you to achieve a higher level of network throughput compared to conventional tree topologies. On the other hand, implementing such a topology requires changes in the network protocol stack of the server;

• extender topology [7], presented in Fig. 3.6 is based on the extended graphs [8].
  

  Figure 3.6 — Extender topology

  It combines all the performance improvements of the "Medusa" topology over the "full tree" topology with higher throughput as the network gradually expands. This topology is created by connecting multiple meta-nodes based on the following rules: first, each meta-node consists of an equal number of ToR switches; secondly, no two ToR-switches are connected within the same meta-node; thirdly, the same number of lines is used to connect each pair of meta-nodes. The advantages of this topology include its structured nature, which increases the predictability of data center states.

  Despite all the above-mentioned advantages of data center topologies, the transition to optical network technologies will allow to provide more bandwidth (Tbit/s in each routable fiber) regardless of the distance. Also, optical switching can be more flexible and, thanks to multi-wavelength routing, it allows not only to improve existing data center topologies, but also to increase service quality parameters.

  Transparent optical networks are connection-oriented networks that can be configured during network operation to best accommodate the volatile traffic of data centers. Compared to electrical switches, optical switches dissipate less heat, resulting in lower cooling costs. In addition, optical switching can seamlessly increase throughput to 100 Gbps and beyond to meet the growing demand for storage.

3.2 Analysis of data center traffic management methods

At the moment there is a fairly large number of works aimed at describing various methods of traffic management, pursuing one or another goal, Figure 3.7.

It is clear from the interaction shown in the figure that depending on the problem posed and the goal pursued, for example, ensuring the quality of service parameters, It is also worth noting that depending on the architecture of optical networks used, it is worth investigating not only the issues of quality of service parameters, but also the issues of survivability.

3.3 Analysis of common strategies for building an optical network with quality of service parameters

For conventional optical networks, survivability is an important parameter. Fast recovery, due to sub-channel protection, for WDM networks is explained in [9]. The principle of this procedure, the following: a large optical network is divided into a smaller domain and the proposed protection of the subchannel, as well as the protection of the common channel.

Survivability in the event of an optical network failure is described in [10]. Obviously, in the situation presented, which arises from natural disasters, a varied approach is necessary.

In the work[11] the scheme of intermediate and preliminary redundancy in elastic optical networks was studied. In [12-13] quality of Service (QoS) protection schemes for flexible optical networks are proposed. In [14] the routing mechanism and assignment of spectrum in elastic optical networks.

Channel and link fault protection/recovery schemes (line and node) in WDM optical networks are presented in [15]. Line and node failure in optical networks leads to simultaneous failure of several optical channels, resulting in a huge loss of data and revenue for the network operator. Wavelength bandwidth requirements for primary and backup route and routing assignments are discussed in [16]. The proposed survivability approach for multiple network failures is also described here, and the switching recovery time and recovery time are explained.

A strategy for restoring shared bandwidth in elastic optical networks is proposed in [17]. In [18] the key features of the survivability of optical networks are analyzed. Network recovery is defined as a network that provides uninterrupted services even after a network failure has occurred. The bandwidth of a fiber-optic network is specified in Gbps and Tbps.

Work [19] deals with the quasi-channel reconstruction scheme, presents the definition of basic network parameters of different topologies (COST239, NSFNET and ARPANET), bandwidth provisioning and resource utilization coefficients.

4 Analysis of Routing and Spectrum Assignment Approaches in Optical Data Center Networks

4.1 Analysis of Routing Approaches in Elastic Optical Data Center Networks

The problem of routing and spectrum assignment in elastic optical networks can be divided into two areas: online and offline RSA. For offline operation, successful RSA requires knowledge of the topology and traffic service requirements in advance. For online operation, the network topology is known in advance, and the traffic service requirements come at random.

For fixed routing, the routes of each source-receiver pair are predefined. When a connection request is received, the algorithms establish a light channel along a predefined route. In minimum-over-routing, the weight of each connection is set to 1, and a route corresponding to the minimum route is selected. In shortest path routing, the physical length of the link is used as the weight, and the path is chosen using shortest path finding algorithms such as Dijkstra's algorithm.

daptive routing algorithms dynamically select routes depending on the state of the network. In this case, unused channels in the network are assigned a single cost, and when a connection request is received, the route with the lowest cost is dynamically selected. To route the least-used path, the connection is determined by the number of free frequency slots available in the channel, and the channel with the maximum available free wavelengths is selected to establish the connection. A power series routing algorithm based on bi-components for adaptive routing, where it can be optimized and adapted to network conditions. In the planning phase, a channel cost function such as normalized channel availability and normalized channel length are used to determine the input variable.

The authors in [20] proposed to formulate a nonlinear programming problem based on channel state for autonomous RSA as a flow problem with multiple goods, considering the constraints of protective carrier in addition to the constraints of spectrum continuity and subcarrier sequence when allocating them according to traffic needs. A solution for the DLC formulation is obtained to minimize the maximum number of subcarriers allocated on any fiber, the maximum subcarrier index allocated on any fiber, and the total number of subcarriers over all fibers. In this work, the authors also calculated the upper and lower bounds of the optimal solution for ring and mesh networks with specified and unspecified routing.

In [21] the authors proposed, close to the channel state, a formulation of the RSA problem known as the routing, wavelength assignment, and spectrum allocation problem. In [22] the authors proposed a routing algorithm that computes several alternative paths for each connection request. The spectrum allocation algorithm is then used to determine the set of available contiguous slots that are assigned to the request. Authors [23] proposed an adaptive routing algorithm to solve the first subtask of the routing tables at each node and associate a probability with each pair. Then the ant colony optimization algorithm is executed continuously, which updates these probabilities based on spectrum usage, and the optimal path is determined. Once the path is chosen, the first fit policy is used to distribute the spectrum.

The authors in [24-25] used an integer programming problem with a spectrum assignment strategy first fit and found an optimal solution to the RSA/RMSA problem using pre-calculated - shortest paths for routing. The simulation result shows that the proposed heuristic reduces the probability of network blocking to 9.4% with a run time of less than one second.

In [27] the authors considered a dynamic version of the RMSA problem, decomposing it into subproblems of dynamic routing rate selection and channel selection. The authors additionally used graph theory to solve the dynamic routing and channel selection problems. In [28] presented two different one-step online RSA algorithms. The first algorithm used a modified Dijkstra shortest-path search algorithm that used channels with enough subcarriers in ascending order of path length. The second one-step RSA algorithm constructs a path vector at the source node such that all channels of each path have sufficient continuous spectrum. The algorithm then searches the path vectors to find the channel with sufficient available spectrum and minimal cost.

The authors in [29] we presented an integer programming model of the static RSA problem in EON in order to minimize the number of subcarriers in EON. The authors also analyzed upper and lower bounds on the maximum number of subcarriers in conventional and ring networks. Two heuristic algorithms balanced spectrum allocation and shortest path with maximum spectrum reuse are proposed to solve the RSA problem in a large network. The simulation result confirms the solution of the integer programming model and heuristic algorithms with optimal resource utilization.

In [30] the authors presented a mixed line rate (MLR) architecture for serving heterogeneous traffic. The authors have developed a mathematical case model for the design of energy efficient and cost effective MLR optical networks. Evaluation of the performance of the developed model under different traffic load scenarios shows that MLR networks can improve the energy efficiency of the network architecture.

The authors in [31] proposed a distance-adaptive routing, spectrum assignment, and reconfiguration algorithm to solve the problem of time-defined request provisioning (DDR) in EOS networks. DDR provisioning requires that data be transmitted within a given time frame without imposing specific bandwidth requirements. Simulation results show significant performance improvements due to bandwidth redistribution. The authors in [32] presented the RSA problem using channels as a set of adjacent subcarriers of a given width to model the spectrum continuity constraint. For a given width of spectrum, all possible channels with subcarriers are defined on each link of the network. The RSA problem is then transformed into a continuous spectrum channel routing and distribution problem. This mechanism leads to a more compact formulation of the integer programming problem, which provides a significant reduction in running time compared to direct spectrum continuity constraints..

The authors[33-34] proposed two RSA algorithms based on -shortest path algorithms using FF to assign spectrum in a dynamic scenario. In [35] the authors presented a three-stage dynamic routing scheme taking into account quality of transmission (QoT), modulation level and spectrum assignment (QoT-aware RSA). Two modified algorithms are used to calculate the path: Dijkstra and the traffic balancing algorithm for spectrum assignment. Simulation results show that the proposed algorithm works efficiently and provides a higher signal-to-noise ratio of the optical signal compared to the FF, RF and SA strategies.

Authors [36-37] used multipath routing, splitting the incoming traffic request into several requests and using several paths for their transmission. Simulation analysis shows that the proposed schemes work more efficiently than single-path routing.

Further research on routing algorithms has shown that additional mechanisms, such as spectrum fragmentation, need to be applied.

4.2 Analysis of spectrum allocation policies for routing

The BLSA algorithm, to reduce the maximum number of subcarriers in the fiber, is based on load balancing. First, the algorithm generates k shortest paths for each source-receiver pair. Then, based on the estimation of the fiber load, the channel is selected. The decision algorithm is simple: the channel whose maximum load is minimal is selected. Spectrum allocation is then performed using assignment strategies: First Fit (FF), Exact Fit (EF) or Random Fit (RF).

The fiber loading can be determined according to formula (4.1):