Если без помощи провайдера, то единственный выход это построить MPLS сеть самому.
1. Для вас самый простой протокол для обмена меток будет LDP.
2. MPLS строится поверх сети IP. Это значит, что на роутерах или комутаторах должна быть настроена IP маршрутизация.
3. Mikrotik и cisco поддерживают MPLS.
4. От туннелей вам не избавиться. Вы не сможете построить MPLS сеть сидя за НАТом. MPLS роутеры должны быть подключены друг к другу физически, если такого подключения нет, то надо построить туннель.
5. Проблемы с MTU. Каждая метка зантмает 4 байта, в пакете могут быть несколько меток. к этому прибавьте еще оверхед от тунеля. Обычно если кто-то и строит MPLS используя туннели, то все выбирают GRE, он занимает 24 байта. Провайдер скорее всего дает вам 1500 MTU минус ваши 28, ваш MTU уже будет 1572 это не считая шифрации.
6. Чтобы построить туннели вам понадобятся белые айпи на всех узлах.
7.
Вот простая схема MPLS, Где PE1 и PE2 это ваши микротики или циски, а AC1-4 могут быть ваши виндовсы и линуксы.
8. MPLS это дорого, не каждый микротик и циско справятся со 100 мб траффиком энкапсулированным в мплс, а потом в гре. Надо будет ставить нормальные железки.
9. MPLS это решение не для вас, во всех смыслах этого слова. (Исходя из задачи, ситуации, ваших знаний)
10. Обычный VPS решает все ваши задачи.
P.S. На клиентских машинах MPLS настраивать не надо, для них будет работать всё как обычно.