The rapidly increasing data usage and overload in mobile broadband networks has driven mobile network providers to actively detect and bill customers who tether tablets and laptops to their mobile phone for mobile Internet access. However, users may not be willing to pay additional fees only because they use their bandwidth differently, and may consider tethering detection as violation of their privacy. Furthermore, accurate tethering detection is becoming harder for providers as many modern smartphones are under full control of the user, running customized, complex software and applications similar to desktop systems. In this work, we analyze the network characteristics available to network providers to detect tethering customers. We present and categorize possible detection mechanisms and derive cost factors based on how well the approach scales with large customer bases. For those characteristics that appear most reasonable and practical to deploy by large providers, we present elimination or obfuscation mechanisms and substantiate our design with a prototype Android App.