Extending TCP for Accelerating Replication on Cluster File Systems over SDNs
Sungheon Lim Hyogon Kim






Extending TCP for Accelerating Replication on Cluster File Systems over SDNs
    Sungheon Lim
Computer Science and Engineering 

Korea University

Seoul, Republic of Korea 

lsh2240@korea.ac.kr
Hyogon Kim
Computer Science 

Korea University

Seoul, Republic of Korea 

hyogon@korea.ac.kr

    
===================================================================================================================================================================================================================




This paper explores the changes required of TCP to efficiently support cluster file systems such as Hadoop Distributed File System (HDFS) where the storage nodes are connected through a software defined networking (SDN). Traditional chain replications in these file systems incur large delay and cause inefficient network use. But SDN can cooperate with the cluster file systems to address the problems by pre-arranging a distribution tree, which opens the possibility of parallel replication. Unfortunately, it cannot be realized without extending TCP, to accommodate the parallel transfer on the transport layer. This paper discusses how to extend TCP to make it possible, and demonstrates the feasibility by implementing a prototype in the Linux kernel. The prototype saves the data replication time by 25% while substantially reducing network use.



TCP extension, Software Defined Networking (SDN), cluster file system, data replication, network utilization, HDFS




§ INTRODUCTION

Today, the data volume stored in data centers is growing explosively. Managing large volumes of data inevitably requires highly automated and efficient technologies. Prominent technologies among them are the large-scale cluster file systems such as Hadoop Distributed File System (HDFS) <cit.>, Google File System (GFS) <cit.>, and Windows Azure Storage <cit.>. Among the prime management concerns for the cluster file systems is data storing operation for its heavy demand. For instance, more than 50% of Facebook tasks in data centers spend their time storing data <cit.> and the amount of traffic to store data accounts for 50% of the total traffic produced in Hadoop clusters <cit.> <cit.>. In this paper, we show that there is an opportunity for optimizing the data storing operation by considering the cooperation of cluster file systems and the SDN, using HDFS as a guiding example for its wide adoption in many data-parallel infrastructures.


In HDFS, fault tolerance is provided by replicating copies in multiple data nodes, with some copies situated on the same rack and others on different racks. Copies are made from node to node using a chain of TCP connections, or `pipeline' <cit.>. This traditional chain replication not only incurs sequential delay but also increases network traffic as the same data may traverse common network paths multiple times. In Figure <ref>, for example, two of the copies are stored in the rack under the top-of-rack (ToR) switch s_a, and one copy in the rack under s_e. Suppose the client that writes the data is in the Internet. If the former copies are made first, the same data traverses twice the link between the data node D_1 and s_a for the in-rack copies. Also, in the transfer from D_2 to D_k for the third copy, three links (i.e., 7,8,9) are duplicately traversed. Even if other paths are taken, the number of traversed links remains the same.



If we let a SDN application consult with the Name Node of HDFS to identify the selected data nodes, however, we can open the possibility of parallel transfer, thereby reducing the cost incurred by the time-consuming and spatially inefficient serial transfers. Specifically, when the client asks the HDFS to store a file, the file system can in turn ask the SDN controller to create a distribution tree (e.g. the thick edges in Figure <ref>) among the involved SDN switches that connect the racks for the selected data nodes. Then the HDFS can transmit the data towards the first node in the pipeline for the chain replication as before, but the pre-arranged SDN distribution paths will mirror them to all data nodes simultaneously, saving time for itself and network resource for other tasks. This arrangement between the Hadoop Name Node and the SDN controller application can be made even in the current standard framework.



Sounding straightforward, however, such parallel transfer cannot be realized without extending TCP. This is because cluster file systems such as HDFS, GFS, and Windows Azure Storage use TCP as the transport protocol, and the SDN-level distribution is done on a lower layer than TCP. Thus the TCP receiver at D_j (j  1) would balk with a reset (RST) upon the data segment directly distributed from the client, as it establishes the connection not with the client but with D_j-1, its direct predecessor in the pipeline. Although one could imagine devising a specialized transport protocol <cit.> <cit.> for this purpose, it would cause backward-compatibility problems. In other words, deployment base for today's widespread cluster file systems would need transition to the new protocol and the application programmers would need to adapt to the model provided by the new protocol. It would be prohibitively expensive, if not impossible. Therefore, we investigate how the TCP protocol can be extended to accommodate the parallel transfer model above, but no change required to the cluster file systems, not to mention the application programmers for them, using HDFS as a guiding example. Furthermore, we implement a proof-of-concept prototype in the Linux kernel, and demonstrate that it indeed leads to significant savings in both time and network use. Specifically, it improves the data transfer time by 25% and saves 15 to 40% traffic for the typical replication factor of 3. But first, we discuss below previous solutions for parallel transfer and their limitation.



§ RELATED WORK



 §.§ Reliable Multicast Protocol

There have been a bunch of researches on reliable multicast protocol for a long time, which provides a reliable sequence of packets to multiple recipients simultaneously. Previous reliable multicast solutions fall into three categories: network-based, sender-based, and receiver-based. ARM <cit.> represents the first category (network-based), which requires the assistance from the network equipment such as routers to support reliable multicast. In ARM, routers suppress duplicate NACKs from multiple receivers to control the implosion problem in the upstream direction and limit the delivery of repair packets to receivers experiencing loss in the downstream direction. In the second category (sender-based), the sender maintains the receivers' information to initiate multicast (e.g. TCP-XM <cit.> and MCTCP <cit.>). Thus, it is usually suitable for the small group. TCP-SMO <cit.>, RMTP <cit.> and RDCM <cit.> represent the last category (receiver-based), where the receivers need to acquire the multicast address in advance so that they can subscribe the multicast group. Especially, in RDCM <cit.>, the author emphasizes on reliable multicast for data centers and points out that existing reliable multicast solutions for the Internet are not suitable for the data center environment. It exploits diverse path existing in data center networks to build backup overlays for peer-to-peer packet repair.



 §.§ Multicast over SDNs

Researches on multicast over SDNs usually focus on multicast routing and management to improve efficiency. MCDC <cit.> suggests multicast routing, in which a SDN controller selects the core routers with the least load. Avalanche <cit.> proposes multicast system, leveraging SDN to take advantage of the rich path diversity commonly available in data center networks while minimizing the size of the routing tree for any given multicast group. Recently, more comprehensive multicast protocols over SDNs are proposed in MCTCP <cit.> and ATHENA <cit.>. The authors in MCTCP <cit.> propose multicast TCP in SDN-based data centers. They exploit SDN as a means of managing IP multicast group and routing. The sender maintains each TCP connections with multiple receivers and moves its sliding window after the slowest receiver sends the acknowledgement (ACK). ATHENA <cit.> enables reliable multicast and congestion control inside SDN based data centers so that no data is lost and other TCP flows in the network are not starved.




 §.§ Existing Problems in the Previous Solutions



Previous solutions break the distributed, or `pipeline', structure originally designed for the cluster file systems and replace it with the multicast structure. 
To be specific, even the HDFS-specific protocols <cit.> <cit.>, not to mention the reliable multicast protocols for the general purpose, insist the multicast structure not only for the data transfer, but also for the ACK transfer including the TCP ACK and the HDFS ACK, which is sent for every HDFS packet in the application layer. It causes realistic problems to exploit previous solutions for parallel transfer in today's widespread cluster file systems. Deployment base for them would need to transition to the new protocol and the application programmers would need to adapt to the model provided by the new protocol. It would be prohibitively expensive, if not impossible and cause backward-compatibility problems. Also, this structure makes the first sender, or the client, take over the distributed ACK processing responsibility from all data nodes in the pipeline, leading to the following problem.

From the perspective of the network, the cost for sending the ACKs becomes more expensive. Especially, the TCP incast problem at the gateway switch (S_c in Figure <ref>) would arise and TCP performance would degrade if the number of data nodes, trying to send the HDFS ACK to the client, reaches only six <cit.>, meaning two clients in the Internet, with the default replication factor of 3. This is because the HDFS ACK is the data from the perspective of TCP. Furthermore, the traveling paths for the ACK become longer, causing more delay. For example, D_2 in Figure <ref> should change its destination for the ACK from D_1 to the client in the Internet.





§ BACKGROUND



 §.§ Software Defined Networking (SDN)

SDN is the architecture that decouples the control and data planes in the network. Control logic is centralized in the so-called SDN controller. By Exploiting this architecture, applications running on the SDN controller operate the network through flow-based forwarding decisions rather than destination-based ones <cit.>. OpenFlow <cit.>, or OpenFlow switch specification is the first standardized protocol in SDN and defines interfaces for the SDN controller to give commands to switches and to receive the network information from them. One of the most common behavior in this standard is the flow entry creation and matching process at SDN switches.



As depicted in Figure <ref>, the SDN controller gives flow-based forwarding rules through  message, including  command, matching field, and actions. Flow is identified by matching field represented as different rectangles in Figure <ref>. Matching field contains IP address, ethernet address, TCP port numbers and so on. The switch does the action specified by the SDN controller to the identified flow. For example, it can modify TCP/IP header and forward the corresponding flow to the designated interface(s).



 §.§ Replication Process

In order to provide the fault tolerance in the cluster file system, it stores the same data in multiple (i.e., 3) nodes. The cluster file system does this process in the application layer. Figure <ref> shows the replication process in HDFS, which is used as a guiding example in this paper.



  * Client requests the Name Node to store a block.

  * The Name Node provides client with the data nodes to store the block.

  * Client asks if D_1 is ready to receive the block (repeated until D_3).

  * D_3 informs to D_2 that pipeline is ready (repeated until client).

  * Client divides the block into multiple HDFS packets and send one of them to D_1 (repeated until D_3).

  * D_3 informs to D_2 that it successfully received the HDFS packet (repeated until client).


5 and 6 are repeated until the block transfer is completed. Even though this process may not exactly same in the other cluster file systems, this process is similar as long as the other cluster file systems use sequential TCP connections for replication like GFS and Windows Azure Storage.









§ DESIGN




 §.§ Challenges

In order to solve the problems mentioned above, we extend TCP over SDNs, and the followings are the key issues in this paper.


  * 

Transparent mirroring with the SDN standard: Unlike previous solutions, our scheme focuses on solving the real-world problem, so it should be feasible in off-the-shelf SDN equipment, supporting the current standard framework.

  * Successful reception of transparently mirrored TCP segments: The mirrored ones are not easy for the next data node in the pipeline to accept, because the TCP header information such as source, destination, and sequence number is not correct.


  * Prevention of duplicate transmission of the transparently mirrored TCP segments: The previous data node in the pipeline tries to send the data already mirrored to the next data node, because the pipeline structure is intact. However, such an action is unnecessary in our scheme.


  * Retransmission of the lost TCP segments: The previous data node in the pipeline does not need to send the data to the next data node, however, if the next data node lose the mirrored TCP segments, the previous data node are required to retransmit the TCP segments like in the original pipeline structure.



Next, we discuss below how the SDN controller application can configure SDN switches to make and forward the transparently mirrored TCP segments towards data nodes.



 §.§ Configuration for Mirroring at SDN Switches

Suppose the Name Node selects the data nodes 𝐃 = {D_1, D_2, …, D_k} for storing a client-requested data, where k is the replication factor. When the Name Node lets the SDN controller application know the pipeline information (IP addresses and TCP port numbers) for 𝐃, it should create flow entries in the switches 𝐒 connecting 𝐃.


  §.§.§ Distributing the Mirrored TCP Segments

At each switch in 𝐒, it creates a flow entry that matches packets from the client to D_1, and performs  action(s) <cit.> on the interface(s) to those data nodes below the given switch. In order to compute the distributing output interface(s), the routing application running on the SDN controller is consulted to obtain the interfaces I_c and I_𝐃 towards the client and 𝐃, respectively. Then, forwarding interfaces are I_𝐃 - I_c. For instance, s_a in Figure <ref> computes {I_D_1,I_D_2} as the forwarding interfaces. Table <ref> summarizes forwarding interfaces at each switch in Figure <ref>.








  §.§.§ Modifying TCP/IP Header for the Transparent Mirroring

In addition to the  action,  actions <cit.> are configured in the ToR switches connecting mirroring data nodes 𝐃-{D_1} down the pipeline. For instance, if a switch needs to deliver the mirrored data to D_j, the  actions modify the IP addresses and the TCP port numbers of the client and D_1 in the source and the destination, respectively, to those of D_j-1 and D_j. Finally, one more  action is configured on the flow entry to set a flag in the reserved field of the TCP header for signaling the receiving TCP that the header has been changed and it is a mirrored copy.

For these configurations at SDN switches, the SDN controller application uses  message to carry the action-creating command  <cit.>. Figure <ref> shows configuration for the transparent mirroring at SDN switches (S_a and S_e) in Figure <ref>.






 §.§ TCP Extentions for Mirrored Replication

The central feature our modified TCP (henceforth TCP “Mirrored Replication (MR)”) is that D_j (2 ≤ j ≤ k) directly receives a HDFS data block from the client, not from the previous data node D_j-1 in the pipeline. To preserve the traditional HDFS chain replication abstraction, however, the pipeline should still be created and maintained. Thus in TCP-MR, the connection from D_j is still established with D_j-1 and the TCP ACKs from D_j is sent to D_j-1 (not to the client), as in the traditional HDFS pipeline. For this reason, when D_j receives a TCP segment from the client (as if from D_j-1), it has to perform two operations in the newly added states (MR_SND and MR_RCV) in Figure <ref>. First, it has to translate the sequence number and accept the payload in the received segment in the MR_RCV state. Second, it should simulate transferring it to D_j+1 down the pipeline in the MR_SND state, while not actually transmitting. Below, we discuss how these two operations are realized in TCP-MR.





  §.§.§ Receiving with Sequence Number Translation

The sequence number spaces are independent between the TCP connections in the pipeline. Figure <ref> shows the pipeline creation process <cit.> from the perspective of TCP (For D_3, similar procedure is repeated). At the last step of the pipeline completion, D_1 informs the client of it <cit.> (a in Figure <ref>), so that the client can start transmitting data (15 in Figure <ref>). But the client first acknowledges the notification-carrying TCP segment from D_1, which is mirrored to all D_j (2 ≤ j ≤ k) (b in Figure <ref>). Then they use the ACK to compute the sequence number compensation given as

    δ_j = n_j - n_1

where n_1 is the sequence number in the mirrored ACK with the reserved flag set to 1,

and n_j is the current sequence number of the TCP channel from D_j-1. For instance, δ_2 is -100 and δ_3 is 300 in Figure <ref>.
From this moment on, TCP-MR on D_j enters into the MR_RCV state in Figure <ref> and accepts the data segments from the client that has the reserved flag set to 1, which signifies that the TCP data segment is a mirrored copy. Meanwhile, for other segments with the reserved flag set, the flags (SYN, ACK, FIN, RST, CWR, ECE) and the ACK number information in the TCP header are ignored because they are the signaling traffic between the client and D_1. But for the TCP segments from D_j-1, for example the retransmissions, D_j processes them normally. Figure <ref> shows the flow chart for receiving process of D_j. Obviously, D_j sends an ACK to D_j-1 as conventional TCP does except setting the reserved flag as 2. D_j-1 receiving the ACK with the reserved flag 2 enters into the MR_SND state in Figure <ref>.









  §.§.§ Simulating Forwarding Down the Pipeline

In order to prevent D_j-1 (2 ≤ j ≤ k) from duplicating the client's transmission to D_j and prepare necessary retransmission in the future, D_j-1 should slide the sending window, run the retransmission timer, and process the ACK from D_j, without actually transmitting data segments. We call this feature of TCP-MR the virtual transmission, and it is done for non-retransmitted data segments. If the retransmission timer expires, however, D_j-1 should actually fill the hole for D_j because the client should not engage with D_j in the chain replication semantics. Table <ref> summarizes differences between TCP and TCP-MR from the perspective of D_j.



Also note that since the data segment comes directly from the client, D_j-1 may receive an ACK from D_j even before its virtual transmission in Figure <ref>, if the following condition holds:




    T_vtx > T_ack


    T_vtx = T_c,j-1 + T_p(j-1)


    T_ack = T_c,j + T_p(j) + T_j,j-1


Here, T_c,j is the time it takes for a TCP segment to travel from the client to D_j, and T_p(j) is the time for D_j to transmit an ACK after receiving the segment. T_p(j-1) is the time for D_j-1 to perform the virtual transmission after receiving a TCP segment from the client. Note that T_p(j-1) > T_p(j) can happen because T_p(j-1) includes the time to receive multiple TCP segments to build a HDFS packet whose default size is 64 KB. In the original Hadoop model, D_j-1 starts to transfer a HDFS packet to D_j only after it completely receives it and notifies the Hadoop application so that it may start the transfer <cit.>. In contrast, T_p(j) includes only the reception and ACK generation delays, which could be much smaller than T_p(j). In case D_j-1 receives an ACK from D_j before it starts the virtual transmission, it first stores the ACK number and processes it upon the virtual transmission, as if it received a normal ACK with the number.


 







§ IMPLEMENTATION AND PERFORMANCE EVALUATION

To prove the feasibility of the proposed concept and evaluate its performance, we implement it on a virtual machine platform using . On a high-performance desktop with Intel  CPU with 8 MB cache and 4.0 GHz clock, we create a virtual machine for each of the client, the data node, the SDN controller, and the Name Node. All are connected to a single SDN switch in a wheel-and-spoke topology. The SDN switch implements the  switch in software as per  <cit.>, and  <cit.> serves as the SDN controller. As for HDFS configurations, the HDFS block size is set to 128 MB, and HDFS packet size to 64 KB. The file size to be stored is set to 128 MB. For each data node, the Linux kernel () is augmented with TCP-MR. We use two metrics for evaluation, HDFS block transfer time and network link use, as we vary the replication factor from 2 to 5. For performance evaluation, we set the maximum kernel memory size for data reception to a sufficient value to prevent throughput drop from having the window size at data nodes reduced to zero. Specifically, we set  to 20 HDFS packets of size 64 KB each, so  is set to 20×64 KB = 1.3 MB.


















 §.§ Block Transfer Time Reduction

Figure <ref> shows the transfer completion times for chain and mirrored replications. `Data' is the net data transfer time, and `total' is the total time including the pipeline setup, etc. We observe that the implemented mirrored replication reduces the data transfer time by 25%, and the total time by 17%. Since the reduction applies to each HDFS data block, the ratio will be the same irrespective of the total file size.
Although the absolute measured times themselves on our simple virtualized testbed may not be too relevant because on a real data center network they can further depend on the network capacity and link congestion levels, the reduction ratios are a meaningful indication of the expected improvement in the real data center environments.







 §.§ Traffic Saving

The parallel transfer by the SDN combined with the non-conventional TCP reception not only saves the time for data write but also the data traffic that crosses the network, which benefits other tasks that share the network resource. We define the total traffic load imposed on the data center network as the volume of the transferred data multiplied by the number of traversed links by it. Given the same data size for the two compared schemes, however, it suffices to count only the number of traversed links L_tot for the comparison. In the traditional chain replication, it can be decomposed to


    L_tot = L_c,s_1 + L_s_1,D_1 + L_D_1,s_2 + ⋯ + L_s_k,D_k

If we let c≡ D_0,

    L_tot = ∑_j=0^k ( L_D_j,s_j+1 + L_s_j+1,D_j+1)


Here, L_x,y denotes the number of intra-datacenter links from x to y, and {s_i}_i=1^k are the (possibly overlapping) ordered list of switches from which the next descending starts towards the next data node in the pipeline. For example, in Figure <ref>, the list is {s_1=s_c,s_2=s_a,s_3=s_c}. Note that the first term in the summation is the number of ascending links going up in the hierarchy, whereas the second term is those descending from the switches to the data nodes. In Figure <ref>, for example, the former links are {5,7,8,9} and the latter are {2,3,4,6,10,11,12} (Link 1 is not in the data center). The idea of the mirrored replication is to eliminate the ascending links in the replication, i.e., the terms L_D_j,s_j+1 (j ≥ 1). 
Therefore, the traffic saving ratio in the proposed system is essentially the fraction of the ascending links in L_tot and the traffic saving ratio is given as


    ∑_j=1^k L_D_j,s_j+1/L_tot



In the typical three-layer switching network that comprise edge (top-of-rack), aggregation, and core switches <cit.> as in Figure <ref>, we can consider two cases: the client is either outside or inside the data center network. In the former, L_c,s_1=0 (we count only the links in the data center network), and the data flow descends through three links. The latter case is further subdivided into four cases. First, if the client colocates with D_1 on the same server, L_D_0,s_1 = L_s_1,D_1 = 0. Moreover, L_D_1,s_2 cannot be eliminated since it should be the replication source. Second, if the client and D_1 are on the same rack but not on the same server, L_D_0,s_1 = L_s_1,D_1 = 1. Third, if they are located in different racks, L_D_0,s_1 = L_s_1,D_1 are either 2 or 3. Otherwise, the number of links can be anywhere between 1 and 3, for both ascending and descending. From D_4 and on, there is no constraint, so it is also anywhere between 1 and 3. Given these, Figure <ref> shows that the average traffic reduction is substantial, ranging from 15 to 40% at the typical replication factor of 3, and likely more for larger replication factors. 






§ DISCUSSION

Our scheme, TCP-MR, is a novel approach in that not only it preserves the pipeline structure during the parallel transfer, as opposed to the previous solutions, in order to reduce data replication time and traffics in the network but also it does stipulate how the SDN switches should work in order to support TCP-MR in the current SDN standard <cit.>. Although it is known to be beneficial for data centers to adopt a SDN <cit.>, its application usually are limited within the network resource management through multicast <cit.> <cit.>, routing <cit.>, switch selection <cit.>, and so on. Meanwhile, in our scheme, SDN switches modify the TCP/IP header and forward the transparently mirrored TCP segments in order to support the TCP extension in a concrete and unprecedented way.

TCP-MR may be concerned with the absence of TCP flow control between the client and D_j (2 ≤ j ≤ k), however, this concern is trivial with the sufficient kernel memory for data reception at D_j. It prevents D_j from dropping the successfully received out-of-order segments to provide the sufficient kernel memory for data reception with D_j. For instance, the mirrored segments from the client may sometimes get lost. Not surprisingly, D_j tries to fill the hole from D_j-1 by sending the TCP ACK and getting the retransmitted segment. During this recovery process, the mirrored out-of-order segments from the client consumes the receive buffer at D_j quickly and the receiver buffer becomes zero. However, the mirrored out-of-order segments keep coming because of the absence of TCP flow control between them. From this moment on, D_j drops even the successfully received out-of-order segments due to no receive buffer and ask D_j-1 to retransmit them. With the sufficient receive buffer, however, D_j does not discard any successfully received segments from the client. The sufficient kernel memory size for HDFS is ×.  is the maximum number of HDFS packets to send without the HDFS ACK in the application layer from all data nodes in the pipeline and it is 20 for default.  is the unit by which HDFS in the application layer divides the data and its default size is 64 KB. Setting aside the kernel memory, which is set manually for performance evaluation, in TCP-MR is necessary for future work.

It is our future work to develop a congestion-aware routing application, tailored to TCP-MR in SDN to complement the absence of TCP congestion control between the client and D_j (2 ≤ j ≤ k). In the SDN architecture, network intelligence such as monitoring congested links and routing to avoid those links is easy to implement because the control and data planes are decoupled <cit.>. Still, TCP-MR has advantages over conventional TCP because paths (i.e., 10,11,12 in Figure <ref>) taken by TCP-MR is the subset of paths (i.e., 7,8,9,10,11,12 in Figure <ref>) taken by conventional TCP.

Some may argue that TCP-MR is only applicable to HDFS, however, it can be applied to any cluster file systems such as GFS and Windows Azure Storage as long as they exploit sequential TCP connections to replicate data. It may require some minor interfacing for adoption, however, there is no burden to application programmers for cluster file systems once it is adopted. As mentioned the above, we used HDFS as a guiding example.

TCP-MR is not comparable to the scheme establishing TCP subflows such as MPTCP because TCP-MR deals with one to many communication whereas MPTCP deals with one to one communication. TCP-MR could be augmented with MPTCP, however, it is beyond the scope of this paper.






§ CONCLUSION

This paper shows that through a TCP extension, the chain replication used in many cluster file systems 
can be performed in parallel among SDN-connected data nodes. The proposed concept preserves the chain replication semantics, which allows HDFS or Hadoop to work without modification. We show by using a prototype implementation that it improves the data transfer time by 25% for typical replication factors. Also, it saves 15 to 40% traffic for the typical replication factor of 3 and more for larger replication factors.


IEEEtran
