Network deduplication (dedup) is an attractive approach to improve network performance for mobile devices. With traditional deduplication, the dedup source uses only the portion of the cache at the dedup destination that it is aware of. We argue in this work that in a mobile environment, the dedup destination (say the mobile) could have accumulated a much larger cache than what the current dedup source is aware of. This can occur because of several reasons ranging from the mobile consuming content through heterogeneous wireless technologies, to the mobile moving across different wireless networks. In this context, we propose asymmetric caching, a solution that is overlaid on baseline network deduplication, but which allows the dedup destination to selectively feedback appropriate portions of its cache to the dedup source with the intent of improving the redundancy elimination efficiency. We show using traffic traces collected from 30 mobile users, that with asymmetric caching, over 89% of the achievable redundancy can be identified and eliminated even when the dedup source has less than one hundredth of the cache size as the dedup destination. Further, we show that the ratio of bytes saved from transmission at the dedup source because of asymmetric caching is over 6× that of the number of bytes sent as feedback. Finally, with a prototype implementation of asymmetric caching on both a Linux laptop and an Android smartphone, we demonstrate that the solution is deployable with reasonable CPU and memory overheads.