Smartphones and tablets have been growing in popularity. These ultra mobile devices bring in new challenges for efficient network operations because of their mobility, resource constraints and richness of features. There is thus an increasing need to adapt network protocols to these devices and the traffic demands on wireless service providers. This dissertation focuses on identifying design limitations in existing network protocols when operating in ultra mobile environments and developing algorithmic solutions for the same. Our work comprises of three components. The first component identifies the shortcomings of TCP flow control algorithm when operating on resource constrained smartphones and tablets. We then propose an Adaptive Flow Control (AFC) algorithm for TCP that relies not just on the available buffer space but also on the application read-rate at the receiver. The second component of this work looks at network deduplication for mobile devices. With traditional network deduplication (dedup), 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. In this context, we propose Asymmetric caching, a solution 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. The third and final component focuses on leveraging network heterogeneity for prefetching on mobile devices. Our analysis of browser history of 24 iPhone users show that URLs do not repeat exactly. Users do show a lot of repetition in the domains they visit but not the particular URL. Additionally, mobile users access web content over diverse network technologies: WiFi and cellular (3G/4G). While data is unlimited over WiFi, users typically have monthly limits on data over the cellular network. In this context, we propose Precog, an action-based prefetching solution to reduce cellular data footprint on smartphones and tablets.