Semi-Random Linear Network Coding for Cloud Storage Redundancy

doi:10.13190/jbupt.201303.31.xiechy

JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM ›› 2013, Vol. 36 ›› Issue (3): 30-34.doi: 10.13190/jbupt.201303.31.xiechy

• Papers • Previous Articles Next Articles

Semi-Random Linear Network Coding for Cloud Storage Redundancy

XIE Chui-yi^1,2, JIA Zhong-tian³, QING Si-han^4,5, LUO Shou-shan¹, CHENG Ming-zhi⁶

1. National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2. School of Mathematics and Information Science, Shaoguan University, Guangdong Shaoguan 512005, China;
3. Shandong Provincial Key Laboratory of Network Based Intelligent Computing, Jinan 250022, China;
4. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;
5. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;
6. College of Information Engineering, Beijing Institute of Graphic Communication, Beijing 102600, China

Received:2012-07-10 Online:2013-06-30 Published:2013-06-30

Abstract

Abstract:

According to structural characteristics and availability requirements of cloud storage, a semi-random linear network coding (SRLNC) algorithm is proposed for data redundancy. The data block is split into pieces, encoded by coding matrix composed of unit row vectors and random row vectors on finite fields GF(2^s), stored in data nodes dispersedly. In decoding process, the data block can be restored with the strategy of unit row vectors priority. The probability of unique solution is analyzed for SRLNC decoding equations, a new operations per character index is defined to measure algorithm efficiency. Experiments prove that the operating time of the decoding process in the proposed algorithm exponentially reduces with the increase of the node availability. When the availability of each node≥0.8 and redundancy≤3, the encoding operation of the proposed algorithm is faster up to 33%, and decoding operation of the proposed is 5 times faster than that of random linear network coding algorithm, respectively. It is shown that the proposed algorithm is applicable to "write once read many" cloud storage system.

Key words: cloud storage, network coding, unit vector, redundancy, operations per character

CLC Number:

TP309.3

XIE Chui-yi, JIA Zhong-tian, QING Si-han, LUO Shou-shan, CHENG Ming-zhi. Semi-Random Linear Network Coding for Cloud Storage Redundancy[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2013, 36(3): 30-34.

[1]	YUAN Jianguo, YU Linfeng, YOU Wei, PANG Yu. An SCL-Flip Decoding Algorithm of Polar Codes to Optimize the Error Pattern Set [J]. Journal of Beijing University of Posts and Telecommunications, 2023, 46(4): 76-82.
[2]	WANG Pu, LIU Chao, BAO Jianrong, JIANG Bin. Information-Aware Layered Weighted Interference Cancellation Coded Caching [J]. Journal of Beijing University of Posts and Telecommunications, 2023, 46(4): 46-51.
[3]	ZHU Hai-long, YAN Yuan-yuan. Measures of Reliability Improvement of Clock Synchronization in Time Sensitive Networking [J]. Journal of Beijing University of Posts and Telecommunications, 2021, 44(2): 20-25,46.
[4]	HE Jian-hua, ZHAO Hui, XU Xiao-bin, YAN Lei, WANG Shang-guang. Data Collection Method of Space-Based Internet of Things Based on Improved Double Level Distributed LT Code [J]. Journal of Beijing University of Posts and Telecommunications, 2020, 43(6): 118-125.
[5]	WEN Wei. Routing Algorithm Based on Density Clustering for Delay Tolerant Network [J]. Journal of Beijing University of Posts and Telecommunications, 2020, 43(5): 137-142.
[6]	ZHANG Rui, ZHU Min, ZHANG Ji, FENG Dan, BAI Bao-ming. Study on 5G Incremental Redundancy HARQ Transmission Strategy [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2018, 41(5): 92-97.
[7]	OU Ze-liang, YANG Hong-wen. An Adaptive Massive MIMO Signal Detection Algorithm Based on Expectation Propagation [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2018, 41(5): 149-152.
[8]	ZHANG Li, YUAN Yu-yu, WANG Cong. FCBF Feature Selection Algorithm Based on Maximum Information Coefficient [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2018, 41(4): 86-90.
[9]	WU Zhan-ji, WU Xi. Survey of Polar Codes for Control Channels in 5G [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2018, 41(4): 110-118.
[10]	YAO Jian-sheng, MA Chun-guang, YUAN Qi, LI Zeng-peng. A Broadcast Transmission Scheme for DTMSN Based on Intra-flow and Inter-flow Network Coding [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2017, 40(5): 18-23.
[11]	QIU Li-ke, GUO Zhong-wen, LIU Qing, LIU Ying-jian, QIU Zhi-jin. Feature Selection Algorithm Based on Redundancy Analysis [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2017, 40(1): 36-41.
[12]	YE Feng, LI Cheng-xin, XU Li, CHEN Jia-zhen, MEN Ai-dong. Perceptual Video Signal Compression Method Based on Structure Analysis [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2016, 39(5): 110-115.
[13]	WANG Jing, LIANG Wei, LIU Xiang-yang, YANG Yang. Locally Repairable Codes Based on MSR Codes in Cloud Storage System [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2016, 39(4): 60-66.
[14]	XIAO Fu, YANG Xie-kun, SUN Li-juan, WANG Ru-chuan, TANG Xiao-xuan. Node Selection Approach for Data Compression in Wireless Multimedia Sensor Networks [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2016, 39(2): 15-19.
[15]	XIAO Da, SU Li-yu, WANG Jun-long, ZHENG Shi-hui, YANG Yu. CSFS: Design and Implementation of Cloud Storage Service-Based File System [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2015, 38(s1): 77-81,86.

Semi-Random Linear Network Coding for Cloud Storage Redundancy

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments