A capability is provided for scaling Redundancy Elimination (RE) middleboxes. The RE middleboxes include an RE encoding middlebox and an RE decoding middlebox. The RE middleboxes may employ max-match-based RE techniques or chunk-match-based RE techniques. The RE middleboxes may utilize Distributed Hash Tables (DHTs) to maintain content stores, respectively. The RE middleboxes may be scaled for use with cloud applications (e.g., for use in transfer of data between a customer network and a cloud side, for use in transfer of data between two cloud sites, or the like).