Циркулянтные сети интенсивно исследуются последние 30 лет и находят широкое применение в различных областях информатики и дискретной математики. По ним два обзора было опубликовано на английском языке (Дж.-К. Бермонда, Ф. Комелласа и Д. Ф. Хсу в 1995 г. и Ф. К. Хванга в 2003 г.) и один на русском языке (О. Г. Монахова и Э.А. Монаховой, 2000 г.). Настоящий обзор дополнительно включает результаты, которые не были отражены в упомянутых источниках, а также новые результаты, полученные в области исследования неориентированных циркулянтных сетей в последние годы.
Скачать электронную версию публикации
Загружен, раз: 69
- Title Структурные и коммуникативные свойства циркулянтных сетей
- Headline Структурные и коммуникативные свойства циркулянтных сетей
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(13)
- Date:
- DOI
Ключевые слова
сети связи, циркулянтные графы, диаметр, маршрутизация, трансляционные и полные обмены, interconnection networks, circulant graphs, diameter, routing, broadcasting and gossipingАвторы
Ссылки
Pelc A. Fault-Tolerant Broadcasting and Gossiping in Communication Networks // Networks. 1996. No. 28. P. 143-156.
Park J.-H. and Chwa K.-Y. Recursive Circulant: a New Topology for Multicomputer Networks // Proc. of the Inter. Symp. on Parallel Architectures, Algorithms, and Networks (I-SPAN'94), Kanazawa, Japan, IEEE Computer Society Press, 1994. P. 73-80.
Parhami B. A Class of Odd-Radix Chordal Ring Networks // J. Comput. Sci. Engin. 2006. V. 4. No. 2-4. P. 1-9.
Parhami B. Chordal Rings Based on Symmetric Odd-Radix Number Systems // Inter. Conf. on Communications in Computing, Las Vegas, NV, June 27-30, 2006. P. 196-199.
Obradovic N., Peters J., and Ruzic G. Reliable Broadcasting in Double Loop Networks // Networks. 2005. V.46. No. 2. P. 88-97.
Narayanan L., Opatrny J., and Sotteau D. All-to-All Optical Routing in Chordal Rings of Degree Four // Algorithmica. 2001. V.31. No. 2. P. 155-178.
Narayanan L. and Opatrny J. Compact routing on chordal rings of degree four // eds. D. Krizanc and P. Widmayer. Sirocco 97: Proc. of the 4th Inter. Colloquium on Structural Information and Communication Complexity, Ascona, Switzerland, Carleton Scientific, 1997. P. 125-137.
Muzychuk M. E. and Tinhofer G. Recognizing circulant graphs of prime order in polynomial time // The Electr. J. Combinat. R25. 1998. V. 5. No. 1. P. 501-528.
Muzychuk M. On Adam's conjecture for circulant graphs // Discr. Math. 1997. V. 167/168. P. 497-510.
Mukhopadhyaya K. and Sinha B. P. Fault-tolerant routing in distributed loop networks // IEEE Trans. Comput. 1995. V.44. No. 12. P. 1452-1456.
Muga F. P. and Yu W. E. A Proposed Topology for a 192-Processor Symmetric Cluster with a Single-Switch Delay // Proceedings of the First Philippine Computing Science Congress. Manila, Philippines, Nov. 2000. 10 p.
Muga F. P. Undirected circulant graphs // Inter. Symp. on Parallel Architectures, Algorithms and Networks. IEEE, 1994. P. 113-118.
Muga F. P. Maximal Order of 3- and 5-Regular Circulant Graphs // Matimyas Matematika. 1999. V. 22. No. 3. 6 p.
Monakhov O. G. and Monakhova E. A. An Algorithm for Discovery of New Families of Optimal Regular Networks // Lect. Notes Artific. Intell. 2003. V.2843. P. 244-254.
Monakhova E. A. Optimal Triple Loop Networks with Given Transmission Delay: Topological Design and Routing // Inter. Network Optimization Conference, (INOC'2003), Evry/Paris, France. 2003. P. 410-415.
Monakhov O. G. and Monakhova E. A. Computer Discovery of Analytical Descriptions of Families of Circulant Networks // 6th Inter. Conf. on Soft Computing and Measurements, (SCM'2003), July 25-27, 2003, St.-Petersburg, Russia, 2003. V. 1. P. 345-348.
Monakhova E. A. Algorithms and lower bounds for p-gossiping in circulant networks // Third Inter. Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'97), Taipei, Taiwan, Dec. 1997, IEEE Computer Society, Los Alamitos, California. P. 132-137.
Monakhova E. A. Optimal circulant computer networks // Inter. Conf. "Parallel Computing Technologies", Novosibirsk, USSR; World Scientific, Singapore, 1991. P. 450-458.
Martinez C., Beivide R., Stafford E., et al. Modeling Toroidal Networks with the Gaussian Integers // IEEE Trans. Comput. 2008. V. 57. No. 8. P. 1046-1056.
Martinez C., Beivide R., Izu C., and Miguel-Alonso J. Characterization of the Class of Optimal Dence Circulant Graphs of Degree Four // XIV Jornadas de Paralelismo. Leganes, Septiembre 2003. P. 1-6.
Mans B. and Shparlinski I. Bisecting and Gossiping in Circulant Graphs // LNCS. 2004. V. 2976. P. 589-598.
Mans B., Pappalardi F., and Shparlinski I. On the spectral Adam property for circulant graphs // Discr. Math. 2002. V.254. No. 1-3. P. 309-329.
Mans B., Pappalardi F., and Shparlinski I. On the Adam Conjecture on Circulant Graphs // LNCS. 1998. V. 1449. P. 251-260.
Mans B. On the Interval Routing of Chordal Rings // Inter. Symposium on Parallel Architectures, Algorithms and Networks (ISPAN 1999), 1999, Australia, IEEE Computer Society. P. 16-21.
Liestman A. L., Opatrny J., and Zaragoza M. Network Properties of Double and Triple Fixed-Step Graphs // Int. J. Found. Comp. Sci. 1998. No. 9. P. 57-76.
Liaw S.-C., Chang G.J., Cao F., and HsuD.F. Fault-tolerant Routing in Circulant Networks and Cycle Prefix Networks // Ann. Comb. 1998. No. 2. P. 165-172.
Li C.H. On isomorphisms of finite Cayley graphs -a survey // Discr. Math. 2002. V. 256. Issues 1-2. P. 301-334.
LaForgeL.E., KorverK.F., and FadaliM.S. What Designers of Bus and Network Architectures Should Know about Hypercubes // IEEE Trans. Comput. 2003. V. 52. No. 4. P. 525-544.
Kotsis G. Interconnection Topologies and Routing for Parallel Processing Systems // Austrian - Hungarian Workhop, Technical Report. KFKI, 1992. P. 95-106.
Jia X.-D. and Su W. Triple Loop Networks with Minimal Transmission Delay // Int. J. Found. Comp. Sci. 1997. V. 8. No. 3. P. 305-328.
Imase M. and Iton M. Desing to minimize diameter building-block networks // IEEE Trans. Comput. 1981. No. C30. P. 439-442.
Hwang F. K. A complementary survey on double-loop networks // Theor. Comp. Sci. 2001. No. 263. P. 211-229.
Hwang F. K. A survey on multi-loop networks // Theor. Comp. Sci. 2003. No. 299. P. 107-121.
HuberK. Codes over Tori // IEEE Trans. Inform. Theor. 1997. V.43. No. 2. P. 740-744.
Hsu D. F. and Shapiro J. A census of tight one-optimal double loop networks // Graph Theory, Combinatorics, Algorithms and Applications / eds. J. Alavi et al. SIAM, 1991. P. 254-265.
Hsu D. F. and Shapiro J. Bounds for the minimal number of transmission delays in double loop networks // J. Combinat., Inform. Syst. Sci. 1991. No. 16. P. 55-62.
Hsu D. F. and Jia X. D. Extremal problems in the combinatorial construction of distributed loop networks // SIAM J. Discr. Math. 1994. No. 7. P. 57-71.
Hedetniemi S. M., Hedetniemi S. T., and Liestman A. L. A survey of gossiping and broadcasting in communication networks // Networks. 1988. No. 18. P. 319-349.
Gomez D., Gutierrez J., Ibeas A., and Beivide R. Optimal routing in double loop networks // Theor. Comp. Sci. 2007. V.381. Issue 1-3. P. 68-85.
Harutyunyan H. A. and Maraachlian E. Near Optimal Broadcasting in Optimal Triple Loop Graphs // IEEE 22nd Inter. Conf. on Advanced Information Networking and Applications, AINA 2008, March 25-29, Ginowan, Okinawa, Japan. P. 167-181.
Gobel F. and Neutel E. A. Cyclic graphs // Discr. Appl. Math. 2000. No. 99. P. 3-12.
Gavoille C. A survey on interval routing // Theor. Comp. Sci. 2000. No. 245. P. 217-253.
Garcia C. and Sole P. Diameter lower bound for Waring graphs and multiloop networks // Discr. Math. 1993. No. 111. P. 257-261.
Feng X. and Xu M. On isomorphisms of Cayley graphs of small valency // Algebra Colloquium. 1994. V. 1. P. 67-76.
Fabrega J. and ZaragozaM. Fault-tolerant routings in double fixed-step networks // Discr. Appl. Math. 1997. No. 78. P. 61-74.
Elspas B. Topological constructions on interconnection limited logic // Switch. Circ. Theor. Log. Des. 1964. No. 164. P. 133-147.
Elspas B. and Turner J. Graphs with circulant adjacency matrices // J. Comb. Theory. 1970. No. 9. P. 229-240.
Du D.-Z., Hsu D. F., Li Q., and Xu J. A combinatorial problem related to distributed loop networks // Networks. 1990. No. 20. P. 173-180.
Davis P. J. Circulant Matrices. New York: Wiley Publ., 1979. 304 p.
Delorme C. and Maheo M. Isomorphisms of cayley multigraphs of degree four on finite abelian groups // Eur. J. Combinat. 1992. No. 13. P. 59-61.
David H. A. Enumeration of cyclic graphs and cyclic designs // J. Comb. Theory. 1972. No. 13. P. 303-308.
Comellas F., Mitjana M., and Peters J. G. Broadcasting in Small-World Communication Networks // 9th Inter. Coll. on Structural Information and Communication Complexity (SIROCCO 9), 2002. Proc. Informatics. 2002. No. 13. P. 73-85.
Chen B.-X., Xiao W.-J., and Parhami B. Diameter formulas for a class of undirected doubleloop networks // J. Intercon. Networks. 2005. V. 6. No. 1. P. 1-15.
Chen B.-X., Meng J.-X., and Xiao W.-J. Some new optimal and suboptimal infinite families of undirected double-loop networks // DMTCS. 2006. No. 8. P. 299-312.
Chen S. and Jia X.-D. Undirected loop networks // Networks. 1993. No. 23. P. 257-260.
Chen B.-X., Meng J.-X., and Xiao W.-J. A Constant Time Optimal Routing Algorithm for Undirected Double-Loop Networks // First Int. Conf. Mobile Ad-hoc and Sensor Networks. MSN 2005, Wuhan, China, December 2005. P. 309-316.
CaiJ.-Y., Havas G., Mans B., et al. On Routing in Circulant Graphs // LNCS. 1999. V. 1627. P. 360-369.
Browne R. F. and Hodgson R. M. Symmetric degree-four chordal ring networks // IEE Proc. 1990. V. 137. No. 4. P. 310-318.
Boesch F. T. and Wang J.-F. Reliable circulant networks with minimum transmission delay // IEEE Trans. Circuits Syst. 1985. No.CAS-32. P. 1286-1291.
Boesch F. T. and Tindell R. Circulants and their connectivity // J. Graph Theory. 1984. No. 8. P. 487-499.
Bermond J.-C. and Tzvieli D. Minimal diameter double-loop networks: Dense optimal families // Networks. 1991. No. 21. P. 1-9.
Bermond J.-C., Illiades G., and Peyrat C. An optimization problem in distributed loop computer networks // Third Inter. Conf. Combinatorial Math. New York, USA, June 1985. Ann. New York Acad. Sci., 1989. No. 555. P. 45-55.
Bermond J.-C., Favaron O., and Maheo M. Hamiltonian decomposition of Cayley graphs of degree four // J. Combin. Theory. Ser. B. 1989. No. 46. P. 142-153.
Bermond J.-C., Comellas F., and Hsu D. F. Distributed loop computer networks: a survey //J. Parallel Distributed Comput. 1995. V.24. P. 2-10.
Beivide R., Martinez C., Izu C., et al. Chordal Topologies for Interconnection Networks // LNCS. 2003. V. 2858. P. 385-392.
Beivide R., Herrada E., Balcazar J. L., and Arruabarrena A. Optimal distance networks of low degree for parallel computers // IEEE Trans. Computers. 1991. V. 40. No. 10. P. 1109- 1124.
Barriere L., Fabrega J., Simo E., and Zaragoza M. Fault-Tolerant Routings in Chordal Ring Networks // Networks. 2000. V.36. No.3. P. 180-190.
Balaban A. T. Reaction graphs // Graph Theoretical Approaches to Chemical Reactivity /eds. D. Bonchev and O. Mekenyan. Netherlands: Kluwer Academic Publishers, 1994. P. 137-180.
Arden B. W. and Lee H. Analysis of chordal ring networks // IEEE Trans. Computers. 1981. No.C-30. P. 291-295.
Aguilo F., Fiol M. A., and Garcia C. Triple Loop Networks with Small Transmission Delay // Discrete Math. 1997. V. 167/168. P. 3-16.
Adam A. Research problem 2-10 // J. Combin. Theory. 1967. No. 2. P. 393.
Яблонский С. В. Алгоритм построения вычислительных сетей с минимальным средним расстоянием между узлами // Тез. докл. Всес. совещ. «Методы и программы решения оптимизационных задач на графах и сетях». Новосибирск, 1980. С. 103-105.
Труфанов С. В. Некоторые задачи о расстояниях на графе // Изв. АН СССР. Техн. кибернетика. 1967. №3. С. 61-66.
Нестеренко Б. Б., Новотарский М. А. Клеточные нейронные сети на циркулянтных графах // Искусственный интеллект. 2009. №3. С. 132-138.
Монахов О. Г., Монахова Э. А. Синтез новых семейств оптимальных регулярных сетей на основе эволюционных вычислений и темплейтов функций // Автометрия. 2004. № 4. С. 106-116.
Монахов О. Г., Монахова Э. А. Параллельные системы с распределенной памятью: структуры и организация взаимодействий. Новосибирск: Изд-во СО РАН, 2000. 242 с.
Монахова Э. А. Об одном экстремальном семействе циркулянтных сетей // Дискрет. анализ и исслед. опер. 2011. Т. 18. №1. С. 66-76.
Монахова Э. А. Мультипликативные циркулянтные сети // Дискрет. анализ и исслед. опер. 2010. Т. 17. №5. С. 56-66.
Монахова Э. А. Оптимальные КАИС-структуры однородных вычислительных систем // Электронное моделирование. 1985. №3. С. 30-34.
Монахова Э. А. Трехмерные циркулянтные сети связи параллельных вычислительных систем // Автометрия. 2006. №3. С. 106-118.
Монахова Э. А. Алгоритмы межмашинных взаимодействий и реконфигурации графов связей в вычислительных системах с программируемой структурой // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1982. №94. С. 81-102.
Монахова Э. А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1981. №90. С. 81-91.
Монахова Э. А. Синтез оптимальных диофантовых структур // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1979. №80. С. 18-35.
Монахов О. Г. Эволюционный синтез алгоритмов на основе шаблонов // Автометрия. Новосибирск, 2006. Т. 42. №1. С. 116-126.
Монахов О. Г. Параметрическое описание структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1979. №80. С. 3-17.
МартинесК., Стаффорд Э., Байвиде Р., Габидулин Э. М. Представление гексагональных созвездий с помощью графов Эйзенштейна - Якоби // Проблемы передачи информации. 2008. Т. 44. №1. С. 3-13.
Корнеев В. В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.
Корнеев В. В. О макроструктуре однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С. 17-34.
Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970. 256 с.
Евреинов Э. В., Хорошевский В. Г. Однородные вычислительные системы. Новосибирск: Наука, 1978. 318 с.
Евдокимов С. А., Пономаренко И. Н. Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время // Алгебра и анализ. 2003. Т. 15. №6. С. 1-34.
Димитриев Ю. К. Анализ самодиагностических свойств структур распределенных живучих вычислительных систем // Автометрия. 1996. №5. С. 71-84.
Воробьев В. А., Корнеев В. В. Некоторые вопросы теории структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С. 3-16.
Воробьев В. А. Простейшие структуры однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С.35-49.
Артамонов Г. Т., Тюрин В. Д. Топология сетей ЭВМ и многопроцессорных систем. М.: Радио и связь, 1991. 248 с.
Артамонов Г. Т. Топология регулярных вычислительных сетей и сред. М.: Радио и связь, 1985. 192 с.
Puente V., Gregorio J.-A., Prellezo J. M., et al. Adaptive Bubble Router: a Design to Balance Latency and Thoughput in Networks for Parallel Computers // Proc. of the 1999 Inter. Conf. on Parallel Processing, ICPP'99, September, 1999. IEEE Computer Society. P. 58-67.
Puente V., Izu C., Gregorio J.-A., et al. Improving Parallel System Performance by Changing the Arrangement of the Network Links // Intern. Conf. on Supercomputing, May 2000, Santa Fe, New Mexico, USA, ACM, 2000. P. 44-53.
Robic B. Optimal routing in 2-jump circulant networks // Tech. Report N397. Cambridge: University of Cambridge Computer Laboratory, 1996. 7 p.
Robic B. and Zerovnik J. Minimum 2-terminal routing in 2-jump circulant graphs // Comput. Artific. Intell. 2000. V. 19. No. 1. P. 37.
Sampels M. Cayley graphs as interconnection networks: A case study // Inter. Conf. Parcella'96. Berlin: Akademie Verlag, 1996. P. 67-76.
Sampels M. Large networks with small diameter // Inter. Workshop on Graph Theoretic Concepts in Computer Science (WG'97). Berlin: Springer, 1997. P.288-302.
Schinder M. New architectures keep pace with throughput needs // Electr. Design. 1981. No. 5. P. 97-106.
Shin K. G. HARTS: A Distributed Real-Time Architecture // Computer. 1991. V. 24. No. 5. P. 25-35.
Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms // Discr. Appl. Math. 1997. No. 77. P. 281-305.
Stone H. S. The organization of high-speed memory for parallel block transfer data // IEEE Trans. Comput. 1970. No. 19. P. 47-53.
Toueg S. and Steiglitz K. The desing of small diameter networks by local search // IEEE Trans. Comput. 1979. No. 28. P. 537-542.
Turner J. Point-symmetric graphs with a prime number of points // J. Combin. Theory. 1967. No.3. P. 136-145.
Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Networks. 1991. No. 21. P. 387-415.
Wilkov R. S. Analysis and design of reliable computer networks // IEEE Trans. Comput. 1972. V. 20. No.3. P. 660-678.
Wong C. K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comput. Mach. 1974. No. 21. P. 392-402.
Wong C. K. and Maddocks T. W. A generalized Pascal's triangle // Fibonacci Quart. 1975. No. 13. P. 134-136.
Yang Y., Funashashi A., Jouraku A., et al. Recursive Diagonal Torus: An Interconnection Network for Massively Parallel Computers // IEEE Trans. Parallel and Distributed Systems. 2001. V. 12. No. 7. P. 701-715.
YebraJ.L.A., FiolM.A., Morillo P., and Alegre I. The diameter of undirected graphs associated to plane tessellations // Ars Combinat. 1985. No.20B. P. 159-172.
Zerovnik J. and Pisanski T. Computing the diameter in multiple-loop networks // J. Algorithms. 1993. No. 14. P. 226-243.
Структурные и коммуникативные свойства циркулянтных сетей | Прикладная дискретная математика. 2011. № 3(13).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 248