4824
правки
P2P: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
'''Оверлейная маршрутизация, вдохновленная сетями типа «Мир тесен»''' | '''Оверлейная маршрутизация, вдохновленная сетями типа «Мир тесен»''' | ||
Алгоритм '''Symphony''' [24] эмулирует маршрутизацию в «тесном» мире. Узлы имеют <math>k</math> связей с узлами, виртуальные идентификаторы которых выбираются случайным образом в соответствии с маршрутизируемым распределением тесного мира [22]. Ожидается, что при <math>k</math> связях Symphony найдет цель за <math>log^2/k</math> переходов. | Алгоритм '''Symphony''' [24] эмулирует маршрутизацию в «тесном» мире. Узлы имеют <math>k</math> связей с узлами, виртуальные идентификаторы которых выбираются случайным образом в соответствии с маршрутизируемым распределением тесного мира [22]. Ожидается, что при <math>k</math> связях Symphony найдет цель за <math>log^2 \; n/k</math> переходов. | ||
| Строка 82: | Строка 82: | ||
Оверлейная схема поиска | {| class="wikitable" style="text-align:center" | ||
Chord | ! Оверлейная схема поиска !! Похожая топология !! Число переходов !! Степень | ||
Viceroy Бабочка log n 5 | |- | ||
AAABMP, сеть с делением расстояний пополам, Koorde, D2B De Bruijn log n 4 | | Chord | ||
Symphony «Тесный мир» | | Гиперкуб | ||
| log n | |||
CAN Тор | | log n | ||
|- | |||
| Viceroy | |||
| Бабочка | |||
| log n | |||
| 5 | |||
|- | |||
| AAABMP, сеть с делением расстояний пополам, Koorde, D2B | |||
| De Bruijn | |||
| log n | |||
| 4 | |||
|- | |||
| Symphony | |||
| «Тесный мир» | |||
| <math>log^2 \; n/k</math> | |||
| k | |||
|- | |||
| SkipGraphs/SkipNet | |||
| Список пропусков | |||
| log n | |||
| log n | |||
|- | |||
| CAN | |||
| Тор | |||
| <math>dn^{1/d}</math> | |||
| d | |||
|} | |||
Таблица 1 | Таблица 1. Сравнение различных показателей схем поиска, не обладающих осведомленностью о локальности | ||
Сравнение различных показателей схем поиска, не обладающих осведомленностью о локальности | |||
