Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Короче говоря, волею судеб оказался я в такси и на своей шкуре испытал все прелести этой работы. Все плюсы и минусы. Из плюсов это свободный график и возможность заниматься чем то еще.
Тут возникла идея создания своего сервиса такси. Начал изучать андроид и java. Одна из задач которые при этом необходимо решить это мониторинг авто и поиск ближайших к клиенту. В то время у самых раскрученных агрегаторов такси("максим “,”везет") все протоколы обмена между приложением и сервером были в незашифрованном виде. Водительское приложение каждые 10-15 секунд отправляет запрос в котором сообщает свое текущее местоположение, статус и т.д. В свою очередь сервер получает заказы от пассажиров и ищет для заказов ближайшие свободные авто. В общем на сервер должны приходить сотни тысяч запросов в секунду т.е. нагрузка, большая и поэтому у агрегаторов каждый город обслуживается своим сервером. У меня возникла идея почему бы всю логику(поиск и т.д.) не перебросить на сторону клиента. Водительское приложение и приложение пассажиров объединяем в одну "P2P overlay" сеть и уже внутри сети производим все необходимые для функционирования сервиса действия.
Каким требованиям должна соответствовать сеть
Это достижимость всех узлов сети
Максимальная скорость передачи пакетов между любыми узлами сети
Отказоустойчивость т.е. сеть должна продолжать функционировать при отключении любого количества узлов
Любой из узлов должен максимально быстро находить физически близкие к нему узлы.
Сеть должна обеспечивать передачу Broadcast и Multicast трафика
Возникают следующие трудности и задачи
все узлы не имеют публичных ip-адресов и находятся за NAT операторов связи
необходим сигнальный сервер посредник который бы сообщал новому узлу A внешние адрес минимум одного узла B , к которому он мог бы присоединиться. Так же сервер сообщает внешний адрес узла A узлу B
Опустим подробности пробивания NAT. Рассмотрим топологию сети.
Представим себе что узлы сети будут физически расположены в одномерном пространстве без пропусков в виде точек, принадлежащих отрезкам на числовой прямой. Самый маленький отрезок и будет у нас единицей измерения в нашей системе координат.
Пронумеруем отрезки в двоичной системе. Заметим что свой номер узел узнает не от сервера(как в IPv4), а вычисляет из данных полученных из другого источника.
Допустим что нам нужно отправить пакет данных из точки (узла) 0000 в точку (узел) 1001. Если все узлы будут знать адреса только смежных узлов, самых близких к себе на числовой прямой, тогда для каждого узла своя локальная карта адресов, узлов с которыми он может связаться, будет выглядеть так:
х это расположение самого узла на своей карте по отношению к др.
т.е. к номеру узла нужно прибавить или отнять единицу .
И пакет пойдет по пути 0000 - 0001 - 0010 - 0011 ит.д. т.е. очень медленно.
Если же узлам сообщать по несколько адресов например для 0000 сообщим адреса 0001 , 0010 ,0100 ,1000 тогда процесс можно ускорить отправив пакет сразу узлу 1000 который в свою очередь отправит его узлу 1001.
Карты будут выглядеть следующим образом:
т.е. к номеру узла нужно прибавить или отнять 1, 2, 4, 8.
Не забываем что все узлы находятся за NAT и чтоб узлы соединились, узлы 0001,0010,0100, 1000 должны знать адрес узла 0000 и наоборот. Так же и для других узлов.
Что мы видим из рисунка 1? То, что первый, второй и третий биты номера отрезка 0110 маленького отрезка (0110-0111) являются номером 011 большого отрезка (0110 -1000), который в свою очередь входит в состав еще большего отрезка(0100-1000) с номером 01 , который в свою очередь входит в состав еще большего отрезка(0000-1000) с номером 0.
Значит адрес узла можно выразить в виде адреса большого отрезка и номеров отрезков вложенных друг в друга. Т.е. если провести аналогию с IP адресацией то большой отрезок 0 будет подсетью в составе сети , отрезок 01 будет подсетью в составе подсети 0, отрезок 011 будет подсетью в составе подсети 01 , а узел 0110 будет в составе подсети 011.
Таким образом мы можем отправить пакет любому участнику сети из любой точки сети.
Узел 0110 будет шлюзом для подсети 011. Узел 0100 будет шлюзом для подсети 01, а узел 0000 будет шлюзом для подсети 0.
Что мы получили в итоге: сеть соответствует требованиям указанным выше кроме пункта 3.
Вопрос поиска ближайших узлов решается самой топологией сети.
Запросы можно отправлять как узлам отдельным так и целым подсетям ( точнее к шлюзу отвечающему за данную подсеть). Так же очевидна возможность масштабирования системы.
Отметим что мы взяли идеальный случай когда узлы равномерно заполняют всю сеть без пропусков. При варианте когда не все отрезки заполнены узлами, ,например узел 10 00 будет отсутствовать , то на его место на карте у всех узлов имеющих связь с узлом 10 00 должен появиться ближайший существующий узел, в нашем случае 1001.
Хорошо с топологией разобрались, что дальше? Реализация
Желание создать сервис такси заказа перетекло в желание создать что то более универсальное ,пригодное для использования в других областях в виде приложений на различных платформах. Решил создать библиотеку на java которая будет отвечать за сетевой уровень OSI. Остальные задачи выше уровнем должны будут решаться приложениями.
Тут собственно и возникает вопрос к аудитории, где можно будет использовать эту библиотеку? Первое что приходит в голову это :
геолокация ,архитектура сети позволяет быстро находить необходимые объекты(курьеры ,авто и т.д.) и отображать их на картах
распределенный поиск, что то вроде "юлы” ,”авито" -"юлавита"
при создании сетевых игр
передачи звука видео , файлов ,другого вида контента от приложения к приложению
систем видеонаблюдения
Что уже готово сейчас и как это работает
Клиент, использующий библиотеку, получает с сервера самый свежий адрес узла, уже присоединенного к сети, создает с ним коннект, через него узнает адреса ближайших узлов и создает с ними соединение.
После этого новоиспеченный участник будет считаться "в сети" и может полноценно функционировать. Что именно он может?
отправлять запросы к определенным узлам и подсетям (как ответ получать list узлов запрашиваемых подсетей). Сеть маршрутизирует запрос с минимальным количеством хопов к адресату.
Для тестирования сети было создано простенькое андроид приложение, которое используя библиотеку отправляет запрос и получает список узлов в определенной подсети или на определенном удалении от себя, в дальнейшем возможна фильтрация узлов по какому-нибудь ключу. Тестирование сети производилось на локальной машине путем создания виртуальных узлов сети.
Над чем еще предстоит поработать
тестирование в реальных условиях (т.е. сервер с реальным IP и клиенты на различных платформах)
уточнить принципы функционирования NAT у различных мобильных операторов и интернет провайдеров так как они скорей всего различны(например время хранения внешних адресов клиента) и насколько сеть будет загружать сети мобильных операторов
вопросы безопасности защищенности самой сети и пользователей
Позвольте, спросите Вы, а как же допущение что все происходит в одномерном пространстве, ведь для определения местонахождения объекта нужно хотя бы две оси координат, а то и все три. Правильно, и над решением этого вопроса пришлось подумать. Как получить сеть с такими же свойствами как у вышеописанной но уже в двухмерном пространстве. Может я что то упустил и решение уже есть? Поэтому прошу уважаемую аудиторию предложить свои варианты. Ну а если кто-то захочет узнать каким образом эту задачу решил я, то после приглашения я с радостью поделюсь своими мыслями и решениями. Заранее благодарен за комментарии.
