Уже немного обсуждалось здесь:
Работа роутера?

Ещё раз повторюсь, немного творчески переработав ответ.
Детекцию раздачи трафика можно условно разделить на несколько рубежей.

1. Рубеж первый
Каждое устройство в сотовой сети в момент регистрации сообщает сети свой IMEI - код устройства, по которому можно однозначно определить модель Вашего устройства.

Да, нужна база IMEI с device capabilities - описанием того, что это за устройство и что оно умеет. Но она у мобильного оператора уже есть: Вам, когда Вы впервые вставляли сим-карту в новый телефон, прилетали SMS-кой настройки интернета? Настройки у разных производителей немного разные, поэтому надо знать модель абонентского аппарата.

Получается, что как только ты вставляешь сим-карту в Wi-Fi-роутер, оператор сразу понимает, что это роутер, а значит, он будет раздавать интернет через Wi-Fi.
Реализация этой технологии оператору обходится совершенно бесплатно.

2. Второй рубеж: анализ TTL.
Надо понимать, что на первом рубеже будут отловлены только собственно роутеры, а включенная в настройках телефона точка доступа Wi-Fi оператору не видна.
Но есть уловка: устройство, раздающее интернет по Wi-Fi, по умолчанию будет уменьшать поле TTL на всех проходящих через него ip-пакетах.
Зная типичные начальные значения TTL для мобильных платформ, можно реагировать на все прочие значения как сигнал, что здесь где-то притаился Wi-Fi.
Для реализации этого, оператору уже потребуются дополнительные расходы.
Понятно, что ставить отдельное устройство для отлова любителей Wi-Fi никто не будет, поэтому обычно этим занимается операторский DPI - комплекс, занимающийся классификацией и "раскраской" абонентского трафика, благодаря которому и становятся возможны, скажем, отдельные условия тарификации социальных сетей.
Кстати, удивительно, но, во-первых, не все DPI это умеют (Эриксон, вам же стыдно, да?). Во-вторых, те, что умеют, умеют это за отдельные деньги в виде подлежащей покупке лицензии.

3. Рубеж третий: эвристика
Тема интересная и увлекательная.
Да, абонент может поменять IMEI прямо в настройках телефона.
Да, абонент может перепрошить телефон, чтобы тот не трогал TTL.
Но, как только хитрых абонентов становится много, оператору становится выгодно вкладываться в расширенный анализ трафика на том же DPI.
Итак, что можно сделать?
Ну, сходу:

3.1. Вы выходите в интернет прямо с телефона через встроенный браузер? Поздравляем, Вы только что в поле User-Agent протокола HTTP рассказали оператору, какая у вас мобильная платформа, и какой версии!
Как так, с одного устройства оператор видит разные User-Agent, указывающие то на Android, то на Apple? Ребята, да у вас там Wi-Fi!

3.2. TCP/IP fingerptinting. Разные мобильные платформы (те же Android/Apple) используют разные начальные значения полей в ip-пакетах. Да взять хоть тот же TCP Window size! Анализируя их, можно угадать как минимум производителя платформы. А комбинируя это с тем же анализом по IMEI...
Ребята, а как так: само устройство у вас от Apple, а значения полей в ip-пакетах характерны для Windows Phone?
Или почему ваш трафик похож то на Android, то на Blackberry?

Понятно, что эвристический анализ реализован тем более не на каждом DPI, и за тем более отдельные деньги за лицензию. Да и производительность подобный анализ просаживает очень здорово...
Однако, технические средства уже есть и, как только они начнут окупаться финансово, оператору становится выгодно их внедрять.

Поскольку резолвинг DNS происходит корректно, промышленно готовых вариантов остаётся три:

1. Провайдерский DPI: наверняка он уже есть у всех провайдеров в том или ином виде.
Логически DPI обычно включается в разрыв линка между ядром и NAT.
Физически зачастую тоже.
Кроме обычных шейпинга и подсчёта трафика per-subscriber, там реализован набор ALG (Application Layer Gateway), которые представляют из себя, фактически, прозрачные прокси для типичных протоколов: HTTP, FTP, DNS и т.д.
Как правило, ALG умеют не только реагировать на определённые значения полей, но и вмешиваться в процесс передачи данных.
Количество ALG зависит от навороченности DPI; в Procera даже World of Warcraft есть )
Ну а уж подмена HTTP-страницы - пожалуй, самая используемая функция HTTP ALG.

2. Наколенное решение раз:
Описано у none7
Завести у себя в сети сервер с ip-адресами, совпадающими с Ip-адресами Вконтакта (ну, или NAT'ить все запросы к нему на сервер-заглушку, что примерно то же самое) - вполне себе решение, если надо заблокировать сервис целиком, а не отдельные страницы на нём.
Но если вдруг ваши политики наберутся дурости у наших, и список блокируемых ресурсов начнёт расти, провайдеры взвоют этот вариант поддерживать )

3. Наколенное решение два:
На самом деле, в России есть свой список блокируемых ресурсов (т.н. список Роскомнадзора) с сотнями тысяч URL.

Выяснилось, что таким количеством записей множество провайдерских DPI попросту давится, поэтому эта задача зачастую решается следующим образом: заводятся отдельные серверы, подключаемые непосредственно к провайдерским BR (Border router'ам).

Задачи серверов:
- заглотить список блокируемых ресурсов, выдрать оттуда имена доменов и разрезолвить их в ip-адреса; адресов получается несколько десятков тысяч
- полученные адреса через OSPF или BGP сливаются в BR. BR - он большой, спокойно держит BGP Full View, поэтому 10-20-50k лишних префиксов для него - капля в море

Получается, что весь трафик в сторону ip-адресов, на которых находится хотя бы одна заблокированная страница, теперь льётся на эти серверы.
Казалось бы, фиг какой сервер всё это переварит, но их можно плодить десятками: срабатывает ECMP/Load Balancing на уровне маршрутизации, и трафик размазывается между серверами примерно поровну.

На самих серверах Linux, а в Linux - squid в transparent mode и iptables )
Соответственно:
- tcp port 80 силами iptables отправляется в сквид, где каждый запрошенный абонентом URL ищется в списке блокированных ресурсов
- в tcp port 443 проверяется SNI чтобы понять, пропускать трафик дальше, или резать к такой-то матери
- весь остальной трафик (и пинги, угу) пропускается насквозь без изменения

Ситуация следующая.
Каждое устройство в сотовой сети в момент регистрации сообщает сети свой IMEI - код устройства, по которому можно однозначно определить модель Вашего устройства.

Да, нужна база IMEI с device capabilities - описанием того, что это за устройство и что оно умеет. Но она у мобильного оператора уже есть: Вам, когда Вы впервые вставляли сим-карту в новый телефон, прилетали SMS-кой настройки интернета? Настройки у разных производителей немного разные, поэтому надо знать модель абонентского аппарата.

Получается, что как только ты вставляешь сим-карту в Wi-Fi-роутер, оператор без дополнительного оборудования понимает, что это роутер, а значит, он будет раздавать интернет через Wi-Fi. Это первый рубеж детекции, и его реализация оператору обходится совершенно бесплатно.

Второй рубеж: анализ TTL, как писал Fixid.
Надо понимать, что на первом рубеже будут отловлены только собственно роутеры, а включенная в настройках телефона точка доступа Wi-Fi оператору не видна.
Но есть уловка: устройство, раздающее интернет по Wi-Fi, по умолчанию будет уменьшать поле TTL на всех проходящих через него ip-пакетах.
Зная типичные начальные значения TTL для мобильных платформ, можно реагировать на все прочие значения как сигнал, что здесь где-то притаился Wi-Fi )
Для реализации этого, оператору уже потребуются дополнительные расходы.
Понятно, что ставить отдельное устройство для отлова любителей Wi-Fi никто не будет, поэтому обычно этим занимается операторский DPI - комплекс, занимающийся классификацией и "раскраской" абонентского трафика, благодаря которому и становится возможен, например, бесплатный вконтакте у некоторых операторов. Но, во-первых, что удивительно, не все DPI это умеют. Во-вторых, те, что умеют, умеют это за отдельные деньги в виде подлежащей покупке лицензии.

Есть и третий рубеж, специально для отлова хитрож... абонентов вроде того же Fixid ;)
Это эвристика.
Тема интересная и увлекательная.
Да, абонент может поменять IMEI прямо в настройках телефона.
Да, абонент может перепрошить телефон, чтобы он не трогал TTL.
Но, как только хитрых абонентов становится много, оператору становится выгодно вкладываться в расширенный анализ трафика.
Итак, что можно сделать?
Ну, сходу:

Вы выходите в интернет прямо с телефона через встроенный браузер? Поздравляем, Вы только что в поле User-Agent протокола HTTP рассказали оператору, какая у вас мобильная платформа, и какой версии!
Как так, с одного устройства оператор видит разные User-Agent, указывающие то на Android, то на Apple? Ребята, да у вас там Wi-Fi!

TCP/IP fingerptinting. Разные мобильные платформы (те же Android/Apple) используют разные начальные значения полей в ip-пакетах. Да взять хоть тот же TCP Window size! Анализируя их, можно угадать как минимум производителя платформы. А комбинируя это с тем же анализом по IMEI...
Ребята, а как так: само устройство у вас от Apple, а значения полей в ip-пакетах характерны для Windows Phone?
Или почему ваш трафик похож то на Android, то на Blackberry?

Умеет это тем более не всякий DPI, и который умеет, умеет за тем более отдельные деньги за лицензию. Да и производительность подобный анализ просаживает очень здорово... Но, тем не менее, если припрёт, это возможно.