基于再生码的云存储系统——Ustor

摘 要：Ustor是一个构建在多个商业云存储服务之上的云存储系统,它旨在保证数据可靠性的同时减少单点失效时占用的修复带宽。不同于将所有数据存储在单个云中,Ustor将数据编码后分布在多个云存储系统中保证可靠性。Ustor的编码模块部署了包括Reed-Solomon码和功能性修复再生码（FRC）在内的多种纠删码,是第一个将功能性修复再生码应用于多个异构的、真实的云存储系统中的应用。与传统的冗余编码比较,FRC显著地减少了单个云存储发生数据丢失时需要从网络上传输的数据量。实验表明：与不编码比较,冗余编码给系统增加了5%~10%的响应时间开销,但可保障节点失效;FRC码编、解码和修复速度与Reed-Solomon码基本相当,256 MB大小文件编码时间差距在0.5 s以内;FRC码修复时与传统的Reed-Solomon码相比减少了25%以上需要下载的数据量。     

基于Fano图的局部循环码构造

为了提高分布式存储系统中数据的可靠性及修复故障节点的可靠性,提出一种基于Fano图的局部循环码。该编码采用了局部性编码的思想,并在局部组内采用基于Fano图的循环码,可以在局部修复组内对故障节点进行快速修复,计算复杂度低。实验结果表明,该编码单节点故障的修复局部性为2,小于现有的RS码与SRC码,且修复带宽开销,与现有的RS码和简单再生码相比具有更低的修复局部性、修复复杂度与修复带宽开销,且修复效率高。     

异构分布式存储系统中部分重复码的构造

部分重复(FR)码因对故障节点提供精确无编码修复,能够提高分布式存储系统的修复效率和可靠性。异构分布式存储系统中FR码的构造更接近于存储数据的实际应用,即每个节点的存储容量和数据块的重复度不同。考虑到用户访问数据的不均衡性,基于数据热度不同重复度不同的思想,文章提出了基于循环置换矩阵(CPMs)与映射置换矩阵(APMs)的异构分布式存储系统中部分重复码的构造。性能分析表明,异构分布式存储系统中的部分重复码可实现存储系统中故障节点的快速修复,具有较低的修复局部性;相对于RS编码以及简单再生码,部分重复码具有更优的修复带宽开销和修复复杂度。     

云灾备的数据修复技术

基于纠错码的云灾备系统的关于降低修复带宽的最新研究成果,文章讨论了云灾备系统中存储节点失效的修复问题。文章指出数据修复问题有3种模型:精确修复、功能修复和系统部分精确修复。在精确修复中,失效的模块需要修复精确的丢失编码包;在功能修复中,新产生的编码包可以包含不同于丢失节点的数据,只要修复的云灾备系统支持最大可分离距离(MDS)码属性。系统部分精确修复是精确修复和部分修复的之间的一个混合的修复模型。     

基于可分组设计的部分重复码研究

针对最小带宽再生情形下的有效修复问题,提出了一种新型部分重复(FR,fractional repetition)码设计。该设计由外部最大距离可分(MDS,maximum distance separable)码和内部重复码组成,称为GDDBFR(group divisible design based FR)码,可以达到随机访问模式下的系统存储容量,并且能够在很大范围内选择构造参数。理论分析指出,尽管GDDBFR码采用基于表格的修复方式,但通常具有大量的节点修复选择方案。此外,实验结果表明,与传统的RS(Reed-Solomon)码和再生码相比,GDDBFR码可以显著地减少失效修复时间。     

基于LT喷泉码的无线传感器网络信息分发协议性能评价

无线传感器网络中,设计可靠的网络协议是困难的.在协议设计中采用纠删码,发送端将数据进行编码并发送,接收端只要接收到足够多的编码包,就能够恢复原始数据包.在TinyOS系统中设计并实现了基于LT喷泉码的信息分发协议,在TOSSIM模拟环境中对其进行了性能评价.模拟结果表明,基于LT喷泉码的信息分发协议能够在降低网络负载的同时提高网络的可靠数据传输.     

网络多播路由的改进编码软件设计与实现

传统网络多播路由编码方法采用多播分布树进行编码,但链路容量遭遇瓶颈,致使编码节点较多,导致浪费带宽资源的问题。在此提出基于Koetter指数时间的网络多播路由改进编码算法对编码软件进行设计,分析多播路由的总体设计,通过数据包编码转发模块在多播拓扑不相交路径上进行编码和转发多播数据包,利用输入模块实现网络多播路由和上游节点的信息交换,通过开关仲裁模块判断能够向特定输出端口传输信息的输入端口,利用死锁控制模块对出现死锁现象的路由节点进行检测,一段时间后使多播路由恢复正常的数据交换,通过输出模块对数据的输出进行管理。以降低带宽资源为目的,采用Koetter指数时间算法实现网络多播路由编码,并给出编码的详细代码。实验结果表明,所提方法不仅节省网络资源,而且显著降低多播路由时延,增强网络吞吐量。     

一种异构分布式存储再生码变换原理

再生码是一类分布式存储编码,由于在节点存储和修复带宽两方面均有效而被广泛研究。基于乘积矩阵(PM)理论的最小存储再生(PM-MSR)码是一类同构分布式存储再生码,具有最小的节点存储。提出一种再生码变换原理,能够根据PM-MSR码产生新的再生码,新的再生码用于异构分布式存储系统。严格证明了新再生码结构的数据重构和数据修复性质,并提供了编码实例。新的再生码与PM-MSR码具有相同的存储消耗和带宽消耗,但新的再生码具有更小的平均节点故障率,这对实际应用具有吸引力。     

无线传感器网络中基于网络嵌入的弱贪婪路由协议

贪婪路由可以划分为强贪婪和弱贪婪2种路由方式。为了解决目前研究工作中弱贪婪路由协议需要地理位置信息,而强贪婪路由协议需要设计满足贪婪属性的网络嵌入图的问题;同时为了降低操作复杂性,减少能量消耗,提出了一种轻量级的基于树的网络嵌入图(TNEG)构建方法。在基于树的网络嵌入图上,设计了具有局部单调性的贪婪函数,并提出了2个路由规则,然后设计了弱贪婪路由协议TGR和基于双树嵌入的路由协议biTGR。模拟实验表明所提路由协议在路径长度和网络负载等性能上具有明显的优势。     

稀疏城市车载网络中的静态结构动态权重路由

以上海市4 000辆出租车为期两年的GPS数据为依托,设计仅存在于理论意义上的车载网络路由最优算法并对其进行仿真,一方面,最优路由算法的结果揭示了现有路由算法的不足;另一方面,根据最优路由算法的宴际路径特点,设计了基于地图的静态结构动态权重的路由策略来逼近车载网络路由的理论最优性能,这一路由算法相对干传统的地理路由和其变种算法在性能方面有超过50%的提升.     

Optimization of link load balancing in multiple spanning tree routing networks

In telecommunication networks based on the current Ethernet technology, routing of traffic demands is based on multiple spanning trees: the network operator configures different routing spanning trees and assigns each demand to be routed in one of the selected spanning trees. A major optimization issue in this solution is the combined determination of (i) a?set of appropriate spanning trees, and (ii) assignment of demands to the trees, in order to achieve an optimal load balancing on the links of the network. In this paper we consider models and solving techniques for lexicographical optimization of two load balancing objective functions. The first objective is the min-max optimization of the n worst link loads (with n up to the total number of network links), and the second objective is the minimization of the average link load (when n is smaller than the total number of network links). Besides exact methods, a heuristic technique that can compute both feasible solutions and lower bounds for the addressed optimization problem is proposed. Finally, we discuss effectiveness of different solution using results of a numerical study of realistic case studies.     

Partially Optimal Routing

Most large-scale communication networks, such as the Internet, consist of interconnected administrative domains. While source (or selfish) routing, where transmission follows the least cost path for each source, is reasonable across domains, service providers typically engage in traffic engineering to improve operating performance within their own network. Motivated by this observation, we develop and analyze a model of partially optimal routing, where optimal routing within subnetworks is overlaid with selfish routing across domains. We demonstrate that optimal routing within a subnetwork does not necessarily improve the performance of the overall network. In particular, when Braess' paradox occurs in the network, partially optimal routing may lead to worse overall network performance. We provide bounds on the worst-case loss of efficiency that can occur due to partially optimal routing. For example, when all congestion costs can be represented by affine latency functions and all administrative domains have a single entry and exit point, the worst-case loss of efficiency is no worse than 25% relative to the optimal solution. In the presence of administrative domains incorporating multiple entry and/or exit points, however, the performance of partially optimal routing can be arbitrarily inefficient even with linear latencies. We also provide conditions for traffic engineering to be individually optimal for service providers.     

Optimal cluster-based routing scheme using node mobility in ad hoc networks

Ad hoc networks have a scalability problem. When the nodes of an ad hoc network increase in number or mobility, the amount of control traffic for routing increases and could cause traffic congestion. Cluster-based routing schemes have been proposed as a solution to this problem. Typical cluster-based ad hoc networks use a proactive routing scheme for intra-cluster routes and a reactive routing scheme for inter-cluster routes. In this study, we propose a new cluster-based routing scheme for ad hoc networks which makes use of the mobility of nodes. Nodes are divided into two groups on the basis of their mobility. For a route search within a cluster, a proactive routing scheme is used for low-mobility nodes and a flooding-based reactive routing scheme is used for high-mobility nodes. The required control traffic of the proposed scheme is analyzed and optimal parameters of the proposed scheme are derived from the analysis. The numerical results show that the proposed scheme produces far less control traffic than a typical cluster-based routing scheme.     

Optimal Heterogeneous Distributed Storage Regenerating Code at Minimum Remote‐Repair Bandwidth Regenerating Point

Recently, a product‐matrix (PM) framework was proposed to construct optimal regenerating codes for homogeneous distributed storage systems (DSSs). In this paper, we propose an extended PM (EPM) framework for coding of heterogeneous DSSs having different repair bandwidths but identical storage capacities. Based on the EPM framework, an explicit construction of minimum remote‐repair bandwidth regenerating (MRBR) codes is presented for a specific heterogeneous DSS, where two geographically different datacenters with associated storage nodes are deployed. The data reconstruction and regeneration properties of the MRBR code are proved strictly. For the purpose of demonstration, an example implementation of MRBR code is provided. The presented MRBR code is the first optimal strict‐regenerating code for heterogeneous DSSs. In addition, our proposed EPM framework can be applied to homogeneous systems also.     

Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks

Traffic engineering aims to distribute traffic so as to "optimize" some performance criterion. This optimal distribution of traffic depends on both the routing protocol and the forwarding mechanisms in use in the network. In IP networks running the OSPF or IS-IS protocols, routing is over shortest paths, and forwarding mechanisms distribute traffic "uniformly" over equal cost shortest paths. These constraints often make achieving an optimal distribution of traffic impossible. In this paper, we propose and evaluate an approach that can realize near optimal traffic distribution without changes to routing protocols and forwarding mechanisms. In addition, we explore the tradeoff that exists between performance and the configuration overhead that our solution requires. The paper's contributions are in formulating and evaluating an approach to traffic engineering in IP networks that achieves near-optimal performance while preserving the existing infrastructure.     

Adaptive load-balancing in WDM mesh networks with performance guarantees

In nowadays, wavelength-division multiplexing (WDM) networks, on the one hand, increasingly more users expect the network to provide high-priority QoS services demanding no congestion and low latency. On the other hand, it is significantly more difficult for network operators to forecast future traffic demands, as the packet traffic running over WDM networks fluctuates over time for a variety of reasons. Confronted with a rough understanding of traffic patterns as well as the increasing number of time-sensitive applications, most networks today are grossly over-provisioned. Thus, designing cost-effective WDM networks in an uncertain traffic environment, which includes network planning and robust routing, is both an important and a challenging task. In this paper, we explore adaptive load-balancing to investigate the problems of network planning and robust routing for WDM mesh networks under varying traffic matrices. We first propose an efficient heuristic algorithm called Maximizing Network Capability (MNC) to provision congestion-free and cost-effective WDM networks based on load-balancing to deal with traffic uncertainty. Then, a novel traffic grooming algorithm called Adding Direct Traffic (ADT) is proposed to implement robust routing with partial traffic information. Finally, we demonstrate by simulation that MNC consumes less resources than previous methods and performs quite close to the optimal solution, while ADT achieves the desirable performance in delay, jitter (delay variation), and throughput compared with existing robust routing and traffic grooming algorithms.     

Evaluation of multicast routing algorithms for real-timecommunication on high-speed networks

Multicast (MC) routing algorithms capable of satisfying the quality of service (QoS) requirements of real-time applications will be essential for future high-speed networks. We compare the performance of all of the important MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC trees it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of real-time applications in wide-area networks. Simulations also reveal that one of the unconstrained algorithms, reverse path multicasting (RPM), is quite inefficient when applied to asymmetric networks. We study how combining routing with resource reservation and admission control improves the RPM's efficiency in managing the network resources. The performance of one semiconstrained heuristic, MSC, three constrained Steiner tree (CST) heuristics, Kompella, Pasquale, and Polyzos (1992), constrained adaptive ordering (CAO), and bounded shortest multicast algorithm (BSMA), and one constrained shortest path tree (CSPT) heuristic, the constrained Dijkstra heuristic (CDKS) are also studied. Simulations show that the semiconstrained and constrained heuristics are capable of successfully constructing MC trees which satisfy the QoS requirements of real-time traffic. However, the cost performance of the heuristics varies. The BSMA's MC trees are lower in cost than all other constrained heuristics. Finally, we compare the execution times of all algorithms, unconstrained, semiconstrained, and constrained     

Oblivious Routing in Fat-Tree Based System Area Networks With Uncertain Traffic Demands

We study oblivious routing in fat-tree-based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by the oblivious performance ratio that bounds the relative performance of the routing algorithm with respect to the optimal algorithm for any given traffic demand. We consider both single-path routing, where only one path is used to carry the traffic between each source-destination pair, and multipath routing, where multiple paths are allowed. For single-path routing, we derive lower bounds of the oblivious performance ratio for different fat-trees and develop routing schemes that achieve the optimal oblivious performance ratios for commonly used topologies. Our evaluation results indicate that the proposed oblivious routing schemes not only provide the optimal worst-case performance guarantees but also outperform existing schemes in average cases. For multipath routing, we show that it is possible to obtain an optimal scheme for all traffic demands (an oblivious performance ratio of 1). These results quantitatively demonstrate the performance difference between single-path routing and multipath routing in fat-trees.     

A novel robust routing algorithm for multi-granularity connection requests in wavelength division multiplexing mesh networks

In this paper, we propose a novel robust routing algorithm based on Valiant load-balancing under the model of polyhedral uncertainty (i.e., hose uncertainty model) for WDM (wavelength division multiplexing) mesh networks. Valiant load-balanced robust routing algorithm constructs the stable virtual topology on which any traffic patterns under the hose uncertainty model can be efficiently routed. Considering there are multi-granularity connection requests in WDM mesh networks, we propose the method called hose-model separation to solve the problem for the proposed algorithm. Our goal is to minimize total network cost when constructing the stable virtual topology that assures robust routing for the hose model in WDM mesh networks. A mathematical formulation (integer linear programming, ILP) about Valiant load-balanced robust routing algorithm is presented. Two fast heuristic approaches are also proposed and evaluated. We compare the network throughput of the virtual topology constructed by the proposed algorithm with that of the traditional traffic grooming algorithm under the same total network cost by computer simulation.