1313
правок
Алгоритмы прямой маршрутизации: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы прямой маршрутизации (посмотреть исходный код)
Версия от 03:48, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 51: | Строка 51: | ||
== Родственные работы == | == Родственные работы == | ||
Единственное более раннее исследование алгоритмов прямой маршрутизации относилось к задаче перестановок на деревьях [3, 13]. В этих статьях было получено время маршрутизации O(n) для любого дерева с n вершинами. Это время является оптимальным в наихудшем случае, тогда как результат в [6] является асимптотически оптимальным для всех задач маршрутизации на деревьях. | Единственное более раннее исследование алгоритмов прямой маршрутизации относилось к задаче перестановок на деревьях [3, 13]. В этих статьях было получено время маршрутизации O(n) для любого дерева с n вершинами. Это время является оптимальным в наихудшем случае, тогда как результат в [6] является асимптотически оптимальным для всех задач маршрутизации на деревьях. | ||
Сайфер и коллеги [7] изучали онлайн-версию задачи прямой маршрутизации, в которой червь (пакет длины L) может быть повторно передан в случае, если он был брошен (они также допускали пропускную способность каналов равной B > | |||
В число других моделей безбуферной маршрутизации входят маршрутизация с сопоставлением [2], при которой пакеты движутся к местам назначения за счет обмена пакетами в смежных узлах, и срочная маршрутизация [4, 5, 8, 9], при которой пакеты следуют по каналам, ведущим их ближе к месту назначения, а если они не могут переместиться ближе из-за конфликтов, они перебрасываются на альтернативные направления. | Сайфер и коллеги [7] изучали онлайн-версию задачи прямой маршрутизации, в которой червь (пакет длины L) может быть повторно передан в случае, если он был брошен (они также допускали пропускную способность каналов равной <math>B \ge 1 \; </math>). Адлер и коллеги [1] изучали задачу прямой маршрутизации с ограничением по времени, в которой требуется спланировать в рамках заданного интервала времени максимальное количество пакетов. Они показали, что версия этой задачи с ограничением по времени является NP-полной, а также рассмотрели аппроксимационные алгоритмы на деревьях и сотовых сетях. Кроме того, был рассмотрен вопрос, насколько буферизация эффективна в решении этой задачи. | ||
В число других моделей безбуферной маршрутизации входят [[маршрутизация с сопоставлением]] [2], при которой пакеты движутся к местам назначения за счет обмена пакетами в смежных узлах, и [[срочная маршрутизация]] [4, 5, 8, 9], при которой пакеты следуют по каналам, ведущим их ближе к месту назначения, а если они не могут переместиться ближе из-за конфликтов, они перебрасываются на альтернативные направления. | |||
== Применение == | == Применение == | ||
| Строка 63: | Строка 65: | ||
== Литература == | == Литература == | ||
1. Adler, M., Khanna, S., Rajaraman, R., Rosen, A.: Time-constrained scheduling of weighted packets on trees and meshes. Algorithmica 36,123-152 (2003) | 1. Adler, M., Khanna, S., Rajaraman, R., Rosen, A.: Time-constrained scheduling of weighted packets on trees and meshes. Algorithmica 36,123-152 (2003) | ||
2. Alon, N., Chung, F., Graham, R.: Routing permutations on graphs via matching. SIAM J. Discret. Math. 7(3), 513-530 (1994) | 2. Alon, N., Chung, F., Graham, R.: Routing permutations on graphs via matching. SIAM J. Discret. Math. 7(3), 513-530 (1994) | ||
3. Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Direct routing on trees. In: Proceedings of the Ninth Annual ACM-SIAM, Symposium on Discrete Algorithms (SODA 98), pp. 342-349. San Francisco, California, United States (1998) | 3. Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Direct routing on trees. In: Proceedings of the Ninth Annual ACM-SIAM, Symposium on Discrete Algorithms (SODA 98), pp. 342-349. San Francisco, California, United States (1998) | ||
4. Ben-Dor, A., Halevi, S., Schuster, A.: Potential function analysis of greedy hot-potato routing. Theor. Comput. Syst. 31(1), 41-61 (1998) | 4. Ben-Dor, A., Halevi, S., Schuster, A.: Potential function analysis of greedy hot-potato routing. Theor. Comput. Syst. 31(1), 41-61 (1998) | ||
5. Busch, C., Herlihy, M., Wattenhofer, R.: Hard-potato routing. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 278-285. Portland, Oregon, United States (2000) | 5. Busch, C., Herlihy, M., Wattenhofer, R.: Hard-potato routing. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 278-285. Portland, Oregon, United States (2000) | ||
6. Busch, C., Magdon-Ismail, M., Mavronicolas, M., Spirakis, P.: Direct routing: Algorithms and Complexity. Algorithmica 45(1), 45-68 (2006) | 6. Busch, C., Magdon-Ismail, M., Mavronicolas, M., Spirakis, P.: Direct routing: Algorithms and Complexity. Algorithmica 45(1), 45-68 (2006) | ||
7. Cypher, R., Meyer auf der Heide, F., Scheideler, C, Vocking, B.: Universal algorithms for store-and-forward and wormhole routing. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 356-365. Philadelphia, Pennsylvania, USA (1996) | 7. Cypher, R., Meyer auf der Heide, F., Scheideler, C, Vocking, B.: Universal algorithms for store-and-forward and wormhole routing. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 356-365. Philadelphia, Pennsylvania, USA (1996) | ||
8. Feige, U., Raghavan, P.: Exact analysis of hot-potato routing. In: IEEE (ed.) Proceedings of the 33rd Annual, Symposium on Foundations of Computer Science, pp. 553-562, Pittsburgh (1992) | 8. Feige, U., Raghavan, P.: Exact analysis of hot-potato routing. In: IEEE (ed.) Proceedings of the 33rd Annual, Symposium on Foundations of Computer Science, pp. 553-562, Pittsburgh (1992) | ||
9. Kaklamanis, C., Krizanc, D., Rao, S.: Hot-potato routing on processor arrays. In: Proceedings of the 5th Annual ACM, Symposium on Parallel Algorithms and Architectures, pp. 273-282, Velen(1993) | 9. Kaklamanis, C., Krizanc, D., Rao, S.: Hot-potato routing on processor arrays. In: Proceedings of the 5th Annual ACM, Symposium on Parallel Algorithms and Architectures, pp. 273-282, Velen(1993) | ||
10. Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes. Morgan Kaufmann, San Mateo(1992) | 10. Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes. Morgan Kaufmann, San Mateo(1992) | ||
11. Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-scheduling in O(congestion+dilation) steps. Combinatorica 14,167-186(1994) | 11. Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-scheduling in O(congestion+dilation) steps. Combinatorica 14,167-186(1994) | ||
12. Leighton, T., Maggs, B., Richa, A.W.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375^01 (1999) | 12. Leighton, T., Maggs, B., Richa, A.W.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375^01 (1999) | ||
13. Symvonis, A.: Routing on trees. Inf. Process. Lett. 57(4), 215-223(1996) | 13. Symvonis, A.: Routing on trees. Inf. Process. Lett. 57(4), 215-223(1996) | ||
14. Valiant, L.G.: A scheme for fast parallel communication. SIAM J.Comput. 11,350-361 (1982) | |||
14. Valiant, L.G.: A scheme for fast parallel communication. SIAM J.Comput. | |||
11,350-361 (1982) | |||
15. Valiant, L.G., Brebner, G.J.: Universal schemes for parallel communication. In: Proceedings of the 13th Annual ACM, Symposium on Theory of Computing, pp. 263-277. Milwaukee, Wisconsin, United States (1981) | 15. Valiant, L.G., Brebner, G.J.: Universal schemes for parallel communication. In: Proceedings of the 13th Annual ACM, Symposium on Theory of Computing, pp. 263-277. Milwaukee, Wisconsin, United States (1981) | ||
[[Категория: Совместное определение связанных терминов]] | |||