Jump to content

Сетевая система координат

Сетевая система координат (система NC) — это система прогнозирования таких характеристик, как задержка или пропускная способность соединений между узлами в сети, путем назначения координат узлам. Более формально, он присваивает вложение координат к каждому узлу в сети с использованием алгоритма оптимизации, такого, что предопределенная операция оценивает некоторую характеристику направления связи между узлом и . [1]

Использование

[ редактировать ]

В общем, сетевые системы координат можно использовать для обнаружения одноранговых узлов, выбора оптимального сервера и маршрутизации с учетом характеристик.

Оптимизация задержки

[ редактировать ]

При оптимизации задержки как характеристики соединения, т. е. для соединений с низкой задержкой, системы ЧПУ потенциально могут помочь улучшить качество работы для многих различных приложений, таких как:

  • Онлайн-игры
    • Формирование игровых групп таким образом, чтобы все игроки находились близко друг к другу и, таким образом, в целом получали более плавный игровой процесс. [2]
    • Выбор серверов как можно ближе к как можно большему количеству игроков в данной многопользовательской игре. [3]
    • Автоматическая маршрутизация игровых пакетов через разные серверы, чтобы минимизировать общую задержку между игроками, активно взаимодействующими друг с другом на игровой карте. [ нужна ссылка ]
  • Сети доставки контента
    • Направление пользователя к ближайшему серверу, который может обработать запрос, чтобы минимизировать задержку. [2] [4]
  • Голос по IP
    • Автоматически переключайте серверы ретрансляции в зависимости от того, кто разговаривает в голосовом чате «несколько ко многим» или «многие ко многим», чтобы минимизировать задержку между активными участниками. [5]
  • Одноранговые сети
    • Может использовать свойства прогнозирования задержки систем NC для выполнения широкого спектра оптимизаций маршрутизации в одноранговых сетях.
  • Сети луковой маршрутизации
    • Выбирайте ретрансляторы, позволяющие минимизировать общую задержку в обоих направлениях и обеспечить более гибкий компромисс между производительностью и анонимностью. [5] [4]
  • Физическое позиционирование
    • Задержка коррелирует с физическими расстояниями между компьютерами в реальном мире. Таким образом, системы ЧПУ, моделирующие задержку, могут помочь определить приблизительную физическую область, в которой находится компьютер. [ нужна ссылка ]

Оптимизация пропускной способности

[ редактировать ]

Системы ЧПУ также могут оптимизировать полосу пропускания (хотя не все конструкции могут добиться этого хорошо). Оптимизация для соединений с высокой пропускной способностью может повысить производительность передачи больших данных. [6] [7] [4]

Обнаружение атак Сивиллы

[ редактировать ]

Атаки Сивиллы вызывают большое беспокойство при разработке одноранговых протоколов. Системы NC с их способностью назначать местоположение источнику трафика могут помочь в создании систем, устойчивых к Сивилле. [8] [9]

Дизайн Пространства

[ редактировать ]

Ориентированное против децентрализованного

[ редактировать ]

Практически любой вариант системы ЧПУ может быть реализован либо в ориентировочной, либо в полностью децентрализованной конфигурации. Системы на основе ориентиров, как правило, безопасны, пока ни один из ориентиров не скомпрометирован, но они не очень масштабируемы. Полностью децентрализованные конфигурации, как правило, менее безопасны, но их можно масштабировать бесконечно.

Евклидово вложение

[ редактировать ]
  • Этот дизайн назначает точку в -мерное евклидово пространство для каждого узла сети и оценивает характеристики с помощью евклидова расстояния . функции где представляет координату узла .
  • Евклидовы конструкции встраивания, как правило, легко оптимизировать.
    • Задача оптимизации сети в целом эквивалентна поиску состояния с наименьшей энергией системы пружина-масса, где координаты масс соответствуют координатам узлов в сети, а пружины между массами представляют собой измеренные задержки между узлами.
    • Чтобы эта функция задачи оптимизации работала в децентрализованном протоколе, каждый узел обменивается своими координатами с координатами фиксированного набора узлов и измеряет задержки для этих узлов, моделируя миниатюрную систему пружинных масс, в которой все массы представляют координаты узла. одноранговые узлы, и каждая масса соединена через одну пружину с собственной «массой» узла, которая при моделировании дает более оптимальное значение координаты узла. Все эти отдельные обновления позволяют сети в целом совместно формировать прогнозируемое координатное пространство.
  • Законы евклидова пространства требуют соблюдения определенных характеристик функции расстояния, таких как симметрия (измерение от должен дать тот же результат, что и из ) и неравенство треугольника . Ни одна из характеристик реальной сети не удовлетворяет полностью этим законам, но некоторые из них делают больше, чем другие. [10] а системы ЧПУ, использующие евклидово встраивание, в некоторой степени точны при работе с наборами данных, содержащими нарушения этих законов. [11] [12] [13]
  • Известные статьи: ВНП , [11] ПОС [12] Вивальди , [13] Фарос [14]

Матричная факторизация

[ редактировать ]
  • Схема матричной факторизации предполагает, что вся сеть представлена ​​неполной матрицей. где — общее количество узлов в сети и любой элемент матрицы на пересечении строк и столбец матрицы представляет собой измерение направленной задержки от узла узел . Цель состоит в том, чтобы оценить числа в незаполненных квадратах матрицы, используя уже заполненные квадраты, т.е. выполнить завершение матрицы . [15]
  • Чтобы оценить конкретную задержку между двумя узлами, этот метод использует скалярное произведение где / представляет собой точку в -мерное внутреннее пространство продукта .
  • Проектирование систем ЧПУ с использованием матричной факторизации обычно сложнее, чем их евклидовые аналоги.
    • В централизованном варианте пополнение матрицы может выполняться непосредственно на наборе ориентиров, которые измерили задержку до каждого другого ориентира в наборе, создавая таким образом полную матрицу. представляющий сеть ориентиров. Затем эту матрицу можно разложить на одном компьютере с помощью факторизации неотрицательных матриц (NNMF) на две матрицы. и такой, что . Поскольку умножение матриц по сути представляет собой скалярное произведение для каждой строки и столбца входных матриц, координаты для каждого ориентира может быть представлен двумя векторами «вход» и «выход» ( и ) взяты соответственно из й ряд и й столбец . При этом задержки между двумя ориентирами можно аппроксимировать простым скалярным произведением: . Любой узел, который хочет определить свои собственные координаты, может просто измерить задержку для некоторого подмножества всех ориентиров, воссоздать полную матрицу, используя координаты ориентира, а затем выполнить NNMF для расчета своей собственной координаты. Эту координату затем можно использовать с любым другим узлом (ориентиром или другим) для оценки задержки до любой другой координаты, которая была рассчитана с использованием того же набора ориентиров. [15] [16]
    • Децентрализованный вариант явно проще. Для данного узла цель состоит в том, чтобы минимизировать абсолютную разницу (или квадратичную разницу) между измеренными задержками для одноранговых узлов и прогнозируемыми задержками для одноранговых узлов. Прогнозируемая задержка определяется тем же уравнением где исходящий вектор узла и это входящий вектор узла . Эту цель (или функцию потерь ) затем можно минимизировать, используя стохастический градиентный спуск с поиском линии . [15]
  • Известные статьи: IDES, [16] Феникс , [17] ДМФСГД [15]

Тензорная факторизация

[ редактировать ]
  • Известные документы: TNDP [18] Использование выборки + персональные устройства [19]

Относительные координаты

[ редактировать ]
  • Известные статьи: RMF [2]

Альтернативы

[ редактировать ]

Сетевые системы координат — не единственный способ прогнозирования свойств сети. Есть также такие методы, как iPlane [20] и iPlane Нано [21] которые используют более аналитический подход и пытаются механически моделировать поведение интернет-маршрутизаторов, чтобы предсказать, по какому маршруту будут проходить некоторые пакеты и, следовательно, какие свойства будет иметь соединение.

В дикой природе

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