Redundancy Elimination Schemes in Computer Communication

Abstract

A large amount of popular content is transferred repeatedly across network links in the Internet. In recent years, protocol-independent redundancy elimination has emerged as a powerful technique to improve the efficiency of network links in the face of repeated data. We conduct a large-scale trace-driven study of protocol independent redundancy elimination mechanisms, driven by several terabytes of packet payload traces. We observe that 35% traffic can be saved by redundancy elimination schemes. ???? Based on the observation we design two redundancy elimination schemes that are EndRE and REfactor. EndRE works as an end system service. It needs to be fast, adaptive and parsimonious in memory usage in order to opportunistically leverage resources on end hosts. Thus, we design a new fingerprinting scheme called SampleByte that is much faster than Rabin fingerprinting while delivering similar compression gains. We show that EndRE delivers 26% bandwidth savings on average, processes payloads at speeds of 1.5-4Gbps, and reduces end-to-end latencies by up to 30%. ???? REfactor is deployed in wireless networks, and leveraged the broadcast nature of wireless radios to improve wireless capacity and performance by removing redundancy. There are two challenges to realize the benefits that are probabilistic nature of wireless reception and the limited resources on wireless devices. We overcome these challenges through careful data structure and wireless redundancy elimination designs. Our evaluations show that it can improve goodput by nearly 25% and air time utilization by nearly 20%.