 |
Here you can view and search the projects funded by NKFI since 2004
Back »
|
 |
Details of project |
|
|
| Identifier |
129589 |
| Type |
KH |
| Principal investigator |
Gulyás, András |
| Title in Hungarian |
Forgalomirányítás nagyméretű hálózatokban |
| Title in English |
Routing in large scale networks |
| Keywords in Hungarian |
routing, nagyméretű hálózatok, forgalomirányítás |
| Keywords in English |
routing, large scale networks |
| Discipline |
| Information Technology (Council of Physical Sciences) | 100 % | | Ortelius classification: Informatics |
|
| Panel |
Informatics and Electrical Engineering |
| Department or equivalent |
Department of Telecommunications and Media Informatics (Budapest University of Technology and Economics) |
| Participants |
Bíró, József
Csikor, Levente
Heszberger, Zalán
Majdán, András
Pašić, Alija
Rétvári, Gábor
Rétvári, Gábor
|
| Starting date |
2018-09-01 |
| Closing date |
2021-08-31 |
| Funding (in million HUF) |
20.000 |
| FTE (full time equivalent) |
2.79 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A kutatási projektben a természetben előforduló (biológiai, szociális, vagy humán-navigációs) és a műszaki területen alkalmazott (Internet) nagy méretű hálózatok működésével kapcsolatos egyik kritikus kérdést, a többutas jelterjedés és útválasztás problémakörét vizsgáljuk. A kutatóközösség egyetért abban, hogy a jelenlegi, kis léptékű hálózatokra optimalizált, a forrás és a célpontok közt egyetlen útvonalra korlátozott kommunikációs sémák, és a kapcsolódó elméleti és gyakorlati keretrendszer, nem ültethetőek át a jövő növekvő, többutas jelterjedést alkalmazó hálózataira. A növekedés itt a hálózat természetes fejlődéséből adódik, míg a többutasság kritériuma a kommunikáció hibatűrési, hatékonysági, és minőségi biztosításának igényéből ered. A kutatás célja egy, a természetbeli hálózatok analíziséből építkező, nagy méretű hálózatokban is skálázható, többutas útválasztási mechanizmus leírása, modellezése, és analízise. A kutatás során feltárjuk az általános értelemben vett jelterjedési útvonalak jellegzetességeit, különös tekintettel a többutas terjedés sajátságaira, majd matematikai keretrendszert definiálunk a feladat formális kezeléséhez, végül előrejelzéseket teszünk a növekvő hálózatok jövőben várható skálázhatóságára és teljesítményére vonatkozóan. A pályázat fő eredménye egy skálázható, többutas, biológia elveken alapuló (biologically inspired) útvonalválasztási architektúra alapelveinek lefektetése a jövőbeli alkalmazások számára.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
Minden hálózat legalapvetőbb funkciója a kommunikáció. Bár a különböző diszciplínákban eltérő elnevezéssel illetik (például szállítás, átvitel, jelzés, csomagtovábbítás, keresés), általánosan igaz, hogy valamilyen kommunikációs út, vagy útvonalak egész halmaza, szükséges ahhoz, hogy a hálózat egy eleme hatást tudjon kifejteni egy másik elemre, amellyel közvetlenül nincs összekötve. Kommunikációs útvonalak híján a csomópontok izoláltan működnének, így nem is beszélhetnénk igazán hálózatról. A valós hálózatokban az átviteli útvonalak halmaza általában nem korlátozódik egyetlen útvonalra: a szociális hálózatokban az információk terjedése általában párhuzamosan, több kapcsolati láncon keresztül történik, az Internetben elterjedten használtak a többutas folyamok, stb. A kommunikációs útvonalak analízise és megismerése ezekben a hálózatokban kiemelt jelentőségű, alig ismert terület. A legtöbb elméleti munka a témában feltételezi, hogy a hálózatokban a kommunikáció a lehetséges legrövidebb út mentén történik. Mérések segítségével (pl. az Interneten) azonban megmutatható, hogy az útvonalak rövidsége csak egy a számos szempont közül, mely két csomópont között meghatározza a kommunikációs útvonalakat. A projekt célja a nagy méretű valós hálózatok többutas jelterjedési mechanizmusainak feltárása, illetve annak valós problémák megoldására történő alkalmazása.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Az elért eredmények várhatóan nem csak a műszaki területen teremtenek majd új alapkutatási irányokat, de olyan más, távolinak tűnő területeken is, mint a biológia vagy a gazdaságtudomány. A kutatómunka első és egyik legfontosabb várható eredménye a valós hálózatokban előforduló kommunikációs stratégiák megértése (az olyan nagy és komplex rendszerekben, mint az Internet, amely milliárdnyi eszközt köt össze, ez kiemelten fontos és nehéz feladat!), illetve ennek mentén annak kimutatása, hogy milyen mechanizmusok segítségével szűkítik a hálózat elemei az elérhető útvonalak halmazát egy jól definiált átviteli úthalmazra, hány különálló útvonalból áll ez a halmaz, mi ezek közt a hasonlóság, stb. Ebben a folyamatban olyan tényezők játszanak szerepet, mint az átviteli úthalmaz (1) maximális függetlensége ("hibatűrés"), (2) lehető legnagyobb összkapacitása ("hatékonyság"), (3) késleltetésének minimalizálása ("minőség"), stb. Ezen felül várható eredmény még olyan útválasztási stratégiák feltérképezése, melyek alkalmazása lehetséges a rendszer méretének intenzív növekedése esetén is. Különösen ígéretesnek tűnik az önszerveződéssel létrejött valós komplex hálózatokban (pl. szociális hálózatok, humán-navigációs sémák) tapasztalt stratégiák Internet architektúrában történő alkalmazása. A kidolgozott matematikai apparátus segítségével az útvonalválasztási és jelterjedési stratégiák minden valós hálózatban egységesen tárgyalhatók. Végül az útválasztási stratégiák hálózat növekedési modellekbe történő integrálása révén választ kaphatunk arra a kérdésre, hogy a jövőbeli hálózatok milyen mértékben lesznek képesek tolerálni a természetes növekedésből adódó terhelésnövekedést. Egy ilyen skálázhatósági modell fontos lenne például az Internet mint kommunikációs hálózat esetében, figyelembe véve a hálózat méretének, a "dolgok internete" (Internet-of-Things, IoT) és az 5. generációs mobilhálózatok küszöbönálló bevezetésének és elterjedésének következtében beálló várható robbanásszerű növekedését.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Számos kutatási eredmény mutat arra, hogy nagy méretű valós hálózatokban (Internet, biológiai hálózatok, gazdasági és szociális hálók) a kommunikáció/jelterjedés egyszerre több független, de alapvetően hasonló jellegzetességeket mutató útvonal mentén történik. Az ilyen rendszerek működésének megértéséhez az útvonalak kialakulásához alkalmazott stratégiák ismerete alapvető jelentőségű. Például az Internet esetében mérésekkel megmutatható, hogy a kialakult adatátviteli útvonalak nem esnek egybe a legrövidebb útvonalakkal, mint ahogy azt a jelenlegi kutatások feltételezik. A nagy méretű természetbeli és mesterséges hálózatokban kialakult összetett útvonalhálózat valódi természetéről igen keveset tudunk. A kutatási projektünk célja a kommunikációs útvonalak pontosabb feltérképezése és ezáltal a valós hálózatokban lezajló kommunikációs folyamatok alaposabb megértése. A kommunikációs folyamatok mélyebb ismereteit felhasználva foglalkozni kívánunk az Internet és egyéb szociális hálózatok természetes növekedéséből adódó kommunikációs problémák leküzdésével. Olyan kérdésekre keresünk választ, mint hogy hogyan terjednek az információk és az (ál-)hírek a szociális hálózatokban, mint a Facebook vagy a Twitter, amely néha váratlan politikai és gazdasági fordulatokhoz vezet (mint az USA elnökválasztás 2017-ben vagy a Brexit), illetve hogy hogyan képesek az emberek megtalálni az információ-továbbítási útvonalakat ezekben az egyre növekvő szociális hálózatokban anélkül, hogy az egész struktúra összeomlana a saját súlya alatt.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The research proposal focuses on one of the most critical issues facing today's large-scale natural (biological, social, or human-navigation) and artificial (the Internet) networks, namely the question of scalable multipath communication schemes. Numerous studies have argued that routing and signaling schemes, and the theoretical models that describe them, which are restricted to a single communications path between sender node and sink nodes and are optimized for small-scale networks, will not be able to cope with ever-extending future networks that are inherently of multipath nature. In this context extension stems from the natural growth of the network, and multipath communications originates from nodes' need for resilience, efficiency, signal quality, and security. The main goal of the project is to develop an empirical understanding and an analytical model for multipath routing in large-scale networks. In the project, we uncover the essential characteristics of signal propagation in large-scale networks with particular attention to the specifics of multipath communications, we develop a solid mathematical model of real world routing policies and systems, and we make predictions regarding the scalability and performance expected in growing real-life natural and artificial networks. The main result of the project is a biologically inspired, scalable multipath route selection scheme for future applications, like the Internet or social networks.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
Communication is one of the most basic functions of any network. Even though different disciplines use different terms, transportation, transshipment, signaling, packet forwarding, or searching, these terms all mark the same thing: that a well-constructed signal propagation path is indispensable for a network element to interact with another one that is not directly connected to it. Without such a path available, network elements are isolated and the network is no longer a functional communications infrastructure, just a bunch of unrelated actors. In real-world networks endpoints usually employ multiple parallel signal propagation paths simultaneously to reach each other: in social networks information and rumors normally spread along multiple independent "friendship" chains, on the Internet communications typically occurs along multiple forwarding paths, etc. Currently, there is very little understanding available as to how (and why) multipath communication routes emerge in large-scale networks. Most theoretical work presumes that communication occurs explicitly along the single shortest (i.e., the least costly) path between a source and the destination, even though empirical proof exists that in the Internet, for instance, communication paths are usually longer ("inflated") than the absolute shortest possible. The ultimate goal of the project is to uncover the underlying rules of multipath routing in large networks, based on a solid understanding and model of the related path selection mechanism, and the application of the results to solve important real world problems.g
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The results achieved in the project are expected to be applicable to a wide area of problems in real world networks (technical, biological, economic, social, etc.), and hopefully will open new areas in basic research. The first and most important objective is to reveal basic communication strategies in real-world networks (a remarkably difficult task in a network connecting potentially billions of nodes, like the Internet!) and to uncover how endpoints of the network collectively restrict the set of available paths between them to only a subset for signal propagation, how many paths such a propagation path set usually contains, and what the overarching scheme across these paths is that would explain why they were picked for signal propagation in the first place. This process is governed by the endpoint's desire to (1) maximize the independence and disjointness of the propagation paths ("failure resilience"), (2) maximize the total parallel communication capacity ("efficiency"), and (3) minimize latency ("quality"), etc. In addition, we also expect our investigations to shed light on the underlying routing strategies and policies that facilitate natural networks to scale to the tremendous size they do. Using the mathematical toolset we develop, we expect to be able to address routing-related problems in natural and artificial networks within the same theoretical framework. Finally, integrating the identified routing strategy models into commonly available network growth models we can obtain an answer to the question to what extent future routing systems will be able to cope with the increasing load resulting from the natural growth of networks. Establishing such a scalability model would be crucial for the Internet above all, considering the exponential extension of the network that we shall witness with the advent of the Internet-of-Things (IoT) and 5G mobile networks.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Recent research indicates that in real-life networks (like the Internet, biological networks, economical and social nets) communications/signal propagation occurs over multiple independent, but characteristically quite similar transmission paths. In order to understand the very operation of such networks it is important to uncover the routing strategies that underlie the observed propagation paths. In the case of the Internet, for example, it was demonstrated that in contrast to widely-held scientific belief communication paths are shaped by much deeper principles than mere path-length minimization. At the moment, there is surprisingly little understanding regarding the true nature of large-scale propagation paths in continuously evolving networks. The goal of the proposed research project is to reveal the governing principles behind the formation of transportation and signaling paths in large-scale complex nets and to develop a deeper understanding of the communication strategies that produce them. The analytical results are to be used to solve the communications problems emerging from the natural growth of some of the fundamental networks that surround us. The questions we investigate are, for instance, how do rumors and (fake) news spread along parallel routes via human social networks (like Facebook or Twitter) which then lead to unexpected political and economic outcomes (like the US presidential election or the Brexit) and how humans somehow magically navigate through this maze of acquaintances without the massive social network just breaking under its own weight.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| On Network Topology Augmentation for Global Connectivity under Regional Failures: János Tapolcai; Zsombor L. Hajdú; Alija Pašić; Pin-Han Ho; Lajos Rónyai, IEEE INFOCOM 2021 - IEEE Conference on Computer Communications, 2021 | | Zongor, L., Heszberger, Z., Pašić, A., & Tapolcai, J.: The Performance of Multi-Path TCP with Overlapping Paths, In Proceedings of the ACM SIGCOMM 2019 Conference Posters and Demos (pp. 116-118). ACM., 2019 | | A. Pašić, R. Girao-Silva, B. Vass, T. Gomes, F. Mogyorósi, P. Babarczi, and J. Tapolcai: FRADIR-II: An Improved Framework for Disaster Resilience, Int. Workshop on Resilient Networks Design and Modeling (RNDM), Nicosia, Cyprus, 2019., 2019 | | Felicián Németh, Marco Chiesa, and Gábor Rétvári: Normal forms for match-action programs, ACM CoNEXT, 2019 | | A. Kőrösi, A. Gulyás, Z. Heszberger, J. Bíró and G. Rétvári: On the Memory Requirement of Hop-by-Hop Routing: Tight Bounds and Optimal Address Spaces, IEEE/ACM Transactions on Networking, vol. 28, no. 3, pp. 1353-1363, 2020 | | Gulyás, A., Bíró, J., Rétvári, G. et al.: The role of detours in individual human navigation patterns of complex networks, Nature Scientific Reports 10, 1098, 2020 | | Alija Pašić, Péter Babarczi, János Tapolcai, Erika Bérczi-Kovács, Zoltán Király, and Lajos Rónyai: Minimum Cost Survivable Routing Algorithms for Generalized Diversity Coding, IEEE/ACM Transactions on Networking (ToN), vol. 28, no. 1, pp. 289-300, 2020 | | Balázs Vass, Erika Bérczi-Kovács, Costin Raiciu, Gábor Rétvári: Compiling Packet Programs to Reconfigurable Switches: Theory and Algorithms, EuroP4'20: Proceedings of the 3rd P4 Workshop in EuropeDecember 2020 Pages 28–35, 2020 | | Ferenc Mogyorósi; Alija Pašić; Richard Cziva; Péter Revisnyei; Zsolt Kenesi; János Tapolcai: Adaptive Protection of Scientific Backbone Networks Using Machine Learning, Published in: IEEE Transactions on Network and Service Management ( Volume: 18, Issue: 1, March 2021), 2021 | | Balazs Vass, Janos Tapolcai, Zalan Heszberger, Jozsef Biro, David Hay, Fernando A. Kuipers, Jorik Oostenbrink, Alessandro Valentini, Lajos Ronyai: Probabilistic Shared Risk Link Groups Modeling Correlated Resource Failures Caused by Disasters, IEEE Journal on Selected Areas in Communications ( Volume: 39, Issue: 9, Sept. 2021), 2021 | | A. Pašić, R. Girão-Silva, F. Mogyorósi, B. Vass, T. Gomes, P. Babarczi, P. Revisnyei, J. Tapolcai, J. Rak: eFRADIR: An Enhanced FRAmework for DIsaster Resilience, IEEE Access ( Volume: 9), 2021 | | Heszberger Zalán, Majdán András, Gulyás András, Gyimóthy Tibor, Bilicki Vilmos, Bíró József: Robust Navigable Cores in the Human Brain Networks, Proc. of The 7th International Conference on Complex Networks and Their Applications, 2018 | | András Gulyás, József Bíró, Gábor Rétvári, Márton Novák, Attila Kőrösi, Mariann Slíz, Zalan Heszberger: The role of detours in individual human navigation patterns of complex networks, PsyArXiv, 2019 | | István Pelle, András Gulyás: An Extensible Automated Failure Localization Framework Using NetKAT, Felix, and SDN Traceroute, FUTURE INTERNET 11 : 5 p. 107, 2019 | | Tapolcai János, Rétvári Gábor, Babarczi Péter, Berczi-Kovács Erika: Scalable and Efficient Multipath Routing via Redundant Trees, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2019 | | Ladóczki Bence, Tapolcai János, Pašić, Alija: Monitoring-Flow Based Network Verification and Failure Localization in Software Defined Networks, In: 38th IEEE International Conference on Computer Communications (INFOCOM), 2019 | | András Gulyás: The role of detours in individual human navigation patterns of complex networks, Proc. of FENS Dynamics of the brain: temporal aspects of computation, Copenhagen, 2019 | | Levente Csikor, Dinil Mon Divakaran, Min Suk Kang, Attila Kőrösi, Balázs Sonkoly, Dávid Haja, Dimitrios P. Pezaros, Stefan Schmid, Gábor Rétvári: Tuple space explosion: a denial-of-service attack against a software packet classifier, CoNEXT '19: Proceedings of the 15th International Conference on Emerging Networking Experiments And TechnologiesDecember 2019 Pages 292–304, 2019 |
|
|
|
|
|
|
|
|
|
