Сетевая система координат
![]() | Эту статью может потребовать очистки Википедии , чтобы она соответствовала стандартам качества . Конкретная проблема: статья полностью в формате списка. ( июнь 2024 г. ) |
Сетевая система координат (система NC) — это система прогнозирования таких характеристик, как задержка или пропускная способность соединений между узлами в сети, путем назначения координат узлам. Более формально, он присваивает вложение координат к каждому узлу в сети с использованием алгоритма оптимизации, такого, что предопределенная операция оценивает некоторую характеристику направления связи между узлом и . [1]
Использование
[ редактировать ]В общем, сетевые системы координат можно использовать для обнаружения одноранговых узлов, выбора оптимального сервера и маршрутизации с учетом характеристик.
Оптимизация задержки
[ редактировать ]При оптимизации задержки как характеристики соединения, т. е. для соединений с низкой задержкой, системы ЧПУ потенциально могут помочь улучшить качество работы для многих различных приложений, таких как:
- Онлайн-игры
- Формирование игровых групп таким образом, чтобы все игроки находились близко друг к другу и, таким образом, в целом получали более плавный игровой процесс. [2]
- Выбор серверов как можно ближе к как можно большему количеству игроков в данной многопользовательской игре. [3]
- Автоматическая маршрутизация игровых пакетов через разные серверы, чтобы минимизировать общую задержку между игроками, активно взаимодействующими друг с другом на игровой карте. [ нужна ссылка ]
- Сети доставки контента
- Голос по IP
- Автоматически переключайте серверы ретрансляции в зависимости от того, кто разговаривает в голосовом чате «несколько ко многим» или «многие ко многим», чтобы минимизировать задержку между активными участниками. [5]
- Одноранговые сети
- Может использовать свойства прогнозирования задержки систем NC для выполнения широкого спектра оптимизаций маршрутизации в одноранговых сетях.
- Сети луковой маршрутизации
- Физическое позиционирование
- Задержка коррелирует с физическими расстояниями между компьютерами в реальном мире. Таким образом, системы ЧПУ, моделирующие задержку, могут помочь определить приблизительную физическую область, в которой находится компьютер. [ нужна ссылка ]
Оптимизация пропускной способности
[ редактировать ]Системы ЧПУ также могут оптимизировать полосу пропускания (хотя не все конструкции могут добиться этого хорошо). Оптимизация для соединений с высокой пропускной способностью может повысить производительность передачи больших данных. [6] [7] [4]
Обнаружение атак Сивиллы
[ редактировать ]Атаки Сивиллы вызывают большое беспокойство при разработке одноранговых протоколов. Системы NC с их способностью назначать местоположение источнику трафика могут помочь в создании систем, устойчивых к Сивилле. [8] [9]
Дизайн Пространства
[ редактировать ]Ориентированное против децентрализованного
[ редактировать ]Практически любой вариант системы ЧПУ может быть реализован либо в ориентировочной, либо в полностью децентрализованной конфигурации. Системы на основе ориентиров, как правило, безопасны, пока ни один из ориентиров не скомпрометирован, но они не очень масштабируемы. Полностью децентрализованные конфигурации, как правило, менее безопасны, но их можно масштабировать бесконечно.
Евклидово вложение
[ редактировать ]- Этот дизайн назначает точку в -мерное евклидово пространство для каждого узла сети и оценивает характеристики с помощью евклидова расстояния . функции где представляет координату узла .
- Евклидовы конструкции встраивания, как правило, легко оптимизировать.
- Задача оптимизации сети в целом эквивалентна поиску состояния с наименьшей энергией системы пружина-масса, где координаты масс соответствуют координатам узлов в сети, а пружины между массами представляют собой измеренные задержки между узлами.
- Чтобы эта функция задачи оптимизации работала в децентрализованном протоколе, каждый узел обменивается своими координатами с координатами фиксированного набора узлов и измеряет задержки для этих узлов, моделируя миниатюрную систему пружинных масс, в которой все массы представляют координаты узла. одноранговые узлы, и каждая масса соединена через одну пружину с собственной «массой» узла, которая при моделировании дает более оптимальное значение координаты узла. Все эти отдельные обновления позволяют сети в целом совместно формировать прогнозируемое координатное пространство.
- Законы евклидова пространства требуют соблюдения определенных характеристик функции расстояния, таких как симметрия (измерение от должен дать тот же результат, что и из ) и неравенство треугольника . Ни одна из характеристик реальной сети не удовлетворяет полностью этим законам, но некоторые из них делают больше, чем другие. [10] а системы ЧПУ, использующие евклидово встраивание, в некоторой степени точны при работе с наборами данных, содержащими нарушения этих законов. [11] [12] [13]
- Известные статьи: ВНП , [11] ПОС [12] Вивальди , [13] Фарос [14]
Матричная факторизация
[ редактировать ]- Схема матричной факторизации предполагает, что вся сеть представлена неполной матрицей. где — общее количество узлов в сети и любой элемент матрицы на пересечении строк и столбец матрицы представляет собой измерение направленной задержки от узла узел . Цель состоит в том, чтобы оценить числа в незаполненных квадратах матрицы, используя уже заполненные квадраты, т.е. выполнить завершение матрицы . [15]
- Чтобы оценить конкретную задержку между двумя узлами, этот метод использует скалярное произведение где / представляет собой точку в -мерное внутреннее пространство продукта .
- Проектирование систем ЧПУ с использованием матричной факторизации обычно сложнее, чем их евклидовые аналоги.
- В централизованном варианте пополнение матрицы может выполняться непосредственно на наборе ориентиров, которые измерили задержку до каждого другого ориентира в наборе, создавая таким образом полную матрицу. представляющий сеть ориентиров. Затем эту матрицу можно разложить на одном компьютере с помощью факторизации неотрицательных матриц (NNMF) на две матрицы. и такой, что . Поскольку умножение матриц по сути представляет собой скалярное произведение для каждой строки и столбца входных матриц, координаты для каждого ориентира может быть представлен двумя векторами «вход» и «выход» ( и ) взяты соответственно из й ряд и й столбец . При этом задержки между двумя ориентирами можно аппроксимировать простым скалярным произведением: . Любой узел, который хочет определить свои собственные координаты, может просто измерить задержку для некоторого подмножества всех ориентиров, воссоздать полную матрицу, используя координаты ориентира, а затем выполнить NNMF для расчета своей собственной координаты. Эту координату затем можно использовать с любым другим узлом (ориентиром или другим) для оценки задержки до любой другой координаты, которая была рассчитана с использованием того же набора ориентиров. [15] [16]
- Децентрализованный вариант явно проще. Для данного узла цель состоит в том, чтобы минимизировать абсолютную разницу (или квадратичную разницу) между измеренными задержками для одноранговых узлов и прогнозируемыми задержками для одноранговых узлов. Прогнозируемая задержка определяется тем же уравнением где исходящий вектор узла и это входящий вектор узла . Эту цель (или функцию потерь ) затем можно минимизировать, используя стохастический градиентный спуск с поиском линии . [15]
- Известные статьи: IDES, [16] Феникс , [17] ДМФСГД [15]
Тензорная факторизация
[ редактировать ]Относительные координаты
[ редактировать ]- Известные статьи: RMF [2]
Альтернативы
[ редактировать ]Сетевые системы координат — не единственный способ прогнозирования свойств сети. Есть также такие методы, как iPlane [20] и iPlane Нано [21] которые используют более аналитический подход и пытаются механически моделировать поведение интернет-маршрутизаторов, чтобы предсказать, по какому маршруту будут проходить некоторые пакеты и, следовательно, какие свойства будет иметь соединение.
В дикой природе
[ редактировать ]Ссылки
[ редактировать ]- ^ Доннет, Бенуа; Гуйе, Бамба; Каафар, Мохамед Али (2010). «Обзор систем сетевых координат, дизайна и безопасности» . Опросы и учебные пособия IEEE по коммуникациям . 12 (4): 488–503. дои : 10.1109/SURV.2010.032810.00007 . ISSN 1553-877X . S2CID 16908400 .
- ^ Перейти обратно: а б с Фу, Юнцюань; Сяопин, Сюй (февраль 2017 г.). «Самостабилизированное прогнозирование расстояния в распределенной сети» . Транзакции IEEE/ACM в сети . 25 (1): 451–464. дои : 10.1109/TNET.2016.2581592 . ISSN 1558-2566 . S2CID 10842765 .
- ^ Агарвал, Шарад; Лорх, Джейкоб Р. (16 августа 2009 г.). «Подбор игроков для онлайн-игр и других P2P-систем, чувствительных к задержкам» . Материалы конференции ACM SIGCOMM 2009 по передаче данных . СИГКОММ '09. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 315–326. дои : 10.1145/1592568.1592605 . ISBN 978-1-60558-594-9 . S2CID 7720412 .
- ^ Перейти обратно: а б с Шерр, Мика; Блейз, Мэтт; Лу, Бун Тау (2009). «Выбор масштабируемого реле на основе каналов для анонимной маршрутизации» . В Голдберге, Ян; Аталлах, Михаил Дж. (ред.). Технологии повышения конфиденциальности . Конспекты лекций по информатике. Том. 5672. Берлин, Гейдельберг: Springer. стр. 73–93. дои : 10.1007/978-3-642-03168-7_5 . ISBN 978-3-642-03168-7 .
- ^ Перейти обратно: а б Шерр, Мика (2009). «Маршрутизация на основе координат для обеспечения высокой анонимности» (PDF) . Компьютерные и информационные науки в Университете Пенсильвании .
- ^ Ляо, Юнджун (11 января 2013 г.). «Научимся прогнозировать сквозную производительность сети» . hdl : 2268/136727 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Рамасубраманиан, Венугопалан; Малхи, Георгин; Кун, Фабиан; Авраам, Иттай; Балакришнан, Махеш; Гупта, Арчит; Акелла, Адитья. «Единая сетевая система координат для пропускной способности и задержки» (PDF) . Исследования Майкрософт .
- ^ Стоккинк, Квинтен; Илери, Джан Умут; Эпема, Дик; Паувелсе, Йохан (01 мая 2023 г.). «Избежание Web3 Sybil с использованием задержки в сети» . Компьютерные сети . 227 : 109701. дои : 10.1016/j.comnet.2023.109701 . ISSN 1389-1286 .
- ^ Чан-Тин, Эрик; Георгиади, Виктор; Хоппер, Николас; Ким, Ёндэ (июль 2015 г.). «Взлом сети Vuze BitTorrent: весь ваш трафик принадлежит нам» . Информационная безопасность ИЭПП . 9 (4): 203–208. doi : 10.1049/iet-ifs.2014.0337 . ISSN 1751-8717 .
- ^ Перейти обратно: а б Ледли, Джонатан; Гарднер, Пол; Зельцер, Марго. «Сетевые координаты в дикой природе» (PDF) . Симпозиум USENIX по проектированию и внедрению сетевых систем (4): 299–311.
- ^ Перейти обратно: а б Нг, ТСЭ; Чжан, Хуэй (июнь 2002 г.). «Прогнозирование расстояния до сети Интернет с помощью подходов, основанных на координатах» . Труды. Двадцать первая ежегодная совместная конференция компьютерных и коммуникационных обществ IEEE . Том. 1. С. 170–179 т.1. дои : 10.1109/INFCOM.2002.1019258 . ISBN 0-7803-7476-2 . S2CID 2967523 .
- ^ Перейти обратно: а б Коста, М.; Кастро, М.; Роустрон, Р.; Ки, П. (март 2004 г.). «PIC: Практические координаты в Интернете для оценки расстояния» . 24-я Международная конференция по распределенным вычислительным системам, 2004 г. Материалы . стр. 178–187. дои : 10.1109/ICDCS.2004.1281582 . ISBN 0-7695-2086-3 . S2CID 846952 .
- ^ Перейти обратно: а б Дабек, Фрэнк; Кокс, Расс; Каашук, Франс; Моррис, Роберт (30 августа 2004 г.). «Вивальди: децентрализованная сетевая система координат» . Обзор компьютерных коммуникаций ACM SIGCOMM . 34 (4): 15–26. дои : 10.1145/1030194.1015471 . ISSN 0146-4833 .
- ^ Ю. Чен; Ю. Сюн; Х. Ши; и др. (апрель 2009 г.). «Фарос: точная и децентрализованная сетевая система координат» (PDF) . ИЭПП Коммуникации . 3 (4): 539–548. дои : 10.1049/iet-com.2008.0187 . S2CID 11701454 . Архивировано из оригинала (PDF) 3 декабря 2013 г. Проверено 27 ноября 2013 г.
- ^ Перейти обратно: а б с д Ляо, Юнджун; Ду, Вэй; Гертс, Пьер; Ледюк, Гай (01 октября 2013 г.). «DMFSGD: децентрализованный алгоритм матричной факторизации для прогнозирования расстояния в сети» . Транзакции IEEE/ACM в сети . 21 (5): 1511–1524. arXiv : 1201.1174 . дои : 10.1109/TNET.2012.2228881 . ISSN 1063-6692 . S2CID 8041240 .
- ^ Перейти обратно: а б Мао, Юн; Сол, Лоуренс К.; Смит, Джонатан М. (декабрь 2006 г.). «IDES: служба оценки расстояния в Интернете для больших сетей» . Журнал IEEE по избранным областям коммуникаций . 24 (12): 2273–2284. дои : 10.1109/JSAC.2006.884026 . ISSN 1558-0008 . S2CID 12931155 .
- ^ Чен, Ян; Ван, Сяо; Ши, Конг; Луа, Энг Кеонг; Фу, Сяомин; Дэн, Пекин; Ли, Син (декабрь 2011 г.). «Феникс: сетевая система координат на основе веса с использованием матричной факторизации» . Транзакции IEEE по управлению сетями и услугами . 8 (4): 334–347. дои : 10.1109/TNSM.2011.110911.100079 . ISSN 1932-4537 . S2CID 8079061 .
- ^ Хуан, Хаоцзюнь; Ли, Ли; Мин, Гейонг; Мяо, Ван; Чжу, Инъин; Чжао, Янмин (ноябрь 2022 г.). «TNDP: тензорное прогнозирование расстояния до сети с доверительными интервалами» . Транзакции IEEE в сфере вычислительных услуг . 15 (6): 3554–3565. дои : 10.1109/TSC.2021.3089241 . hdl : 10871/127476 . ISSN 1939-1374 . S2CID 236311001 .
- ^ Дэн, Лей; Чжэн, Хайфэн; Лю, Сяо-Ян; Фэн, Синьсинь; Чен, Чжичжан Дэвид (15 декабря 2020 г.). «Оценка сетевой задержки с использованием выборки рычагов для персональных устройств: адаптивный тензорный подход к завершению» . Транзакции IEEE/ACM в сети . 28 (6): 2797–2808. дои : 10.1109/TNET.2020.3022757 . ISSN 1063-6692 . S2CID 226411480 .
- ^ Мадхьястха, Харша В.; Исдал, Томас; Пятек, Майкл; Диксон, Колин; Андерсон, Томас; Кришнамурти, Арвинд; Венкатарамани, Арун (6 ноября 2006 г.). «iPlane: информационная плоскость для распределенных услуг» (PDF) . Материалы 7-го симпозиума по проектированию и внедрению операционных систем . ОСДИ '06. США: Ассоциация USENIX: 367–380. ISBN 978-1-931971-47-8 . Архивировано из оригинала 26 января 2023 г.
- ^ Мадхьястха, Харша В.; Кац-Бассетт, Итан; Андерсон, Томас; Кришнамурти, Арвинд; Венкатарамани, Арун (22 апреля 2009 г.). «iPlane Nano: прогнозирование пути для одноранговых приложений» . Материалы 6-го симпозиума USENIX по проектированию и внедрению сетевых систем . НСДИ'09. США: Ассоциация USENIX: 137–152.
- ^ Чан-Тин, Эрик; Георгиади, Виктор; Хоппер, Николас; Ким, Ёндэ (июль 2015 г.). «Взлом сети Vuze BitTorrent: весь ваш трафик принадлежит нам» . Информационная безопасность ИЭПП . 9 (4): 203–208. doi : 10.1049/iet-ifs.2014.0337 . ISSN 1751-8717 .