 |
The geometric theory of network routing
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
104939 |
| Type |
PD |
| Principal investigator |
Rétvári, Gábor |
| Title in Hungarian |
A hálózati útvonalválasztás geometriai elmélete |
| Title in English |
The geometric theory of network routing |
| Keywords in Hungarian |
Internet, útvonalválasztás, alkalmazott geometria, lineáris programozás, forgalommenedzsment |
| Keywords in English |
Internet, routing, computational geometry, linear programming, traffic engineering |
| Discipline |
| Telecommunication (Council of Physical Sciences) | 90 % | | Ortelius classification: Telecommunications engineering | | Operational Research (Council of Physical Sciences) | 10 % | | Ortelius classification: Operations research |
|
| Panel |
Informatics and Electrical Engineering |
| Department or equivalent |
Department of Telecommunications and Media Informatics (Budapest University of Technology and Economics) |
| Starting date |
2012-10-01 |
| Closing date |
2015-09-30 |
| Funding (in million HUF) |
16.896 |
| FTE (full time equivalent) |
2.40 |
| 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 jelen kutatási terv célja egy új geometriai modell kidolgozása, amely betekintést enged a hálózati útválasztás alapvető összefüggéseibe és levetővé teszi az erőforrásokért versengő forgalmak viselkedésének újfajta analízisét, továbbá olyan útválasztási módszerek kidolgozását, melyek segítenek minimalizálni ezt a versengést. Mindezt egy különleges megközelítés teszi lehetővé, mely a hálózat erőforrásaihoz és az útválasztó algoritmusokhoz geometriai objektumokat rendel, és ezeken a objektumokon keresztül írja le azok kölcsönhatásait. Ez a megközelítés a modellezés, a matematikai analízis, az algoritmustervezés, és a numerikus módszerek egészen új lehetőségeit nyitja meg, mivel a hálózatok leírására eddig használatos, többnyire *algebrai* jellegű elméleteket, úgy mint a hálózati folyamok elmélete, lineáris programozás, stb., egy alapvetően *geometriai* szemlélettel egészíti ki. A geometriai megközelítés már eddig is lehetővé tette több, korábban megválaszolhatatlannak bizonyuló elméleti kérdés tisztázását, például választ adott arra a fundamentális kérdésre, hogy létezik-e útvonalaktól független fair erőfoglalás-allokáció. Meggyőződésem tehát, hogy amennyiben sikerül a kapcsolódó elméleti és gyakorlati módszereket teljes mélységükben kidolgozni, úgy a hálózatokat leíró geometria elmélete hatékony új eszközt adhat a mérnökök kezébe a jövő hálózatainak megtervezéséhez.
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.
A kutatás alaphipotézise, hogy a hálózati útválasztás alapvető kérdései mögött meghúzódik egy igen jelentős geometriai tartalom. Azt gondolom, hogy ahogy a geometria korábban hatékony eszköznek bizonyult absztrakt algebrai kérdések vizsgálatában, vagy ahogy a differenciális geometria segít a relativisztikus fizika megértésében, úgy a hálózati útválasztás kérdései mögött is kereshetünk mély geometriai fogalmakat. Ennek a hipotézisnek az alapja az a tény, hogy a korábbi kutatásaim során kiderült, hogy létezik egy természetes megfeleltetés az egyes hálózatok és az azokon átvihető fogalmi mátrixok, illetve egy absztrakt geometriai tér és az abban definiált egyszerű geometriai objektumok, konkrétan poliéderek között. A hálózaton végzett minden műveletnek létezik egy ekvivalens művelete a geometriai térben, és sok esetben tapasztaltam, hogy a geometriai interpretáció lényegesen érthetőbb és analizálhatóbb mentális modellt ad mint a folyamelméleti. A pályázat legfontosabb célja a geometriai modell kidolgozása, megértése, és a kapcsolatos analitikus és numerikus technikák kidolgozása, illetve azok alkalmazása néhány, mind gyakorlati mind elméleti szempontból létfontosságú probléma megválaszolására.
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!
A geometria valamilyen formája szinte minden tudományágban, előbb vagy utóbb, megjelenik. Igaz ez a mégoly elvont területekre is, mint az algebra. Ennek oka, meglátásom szerint, hogy a geometria olyan absztrakciókat kínál, a terek, pontok, egyenesek, szögek, a geometria axiómái illetve a geometriai transzformációk formájában, melyekhez gyermekkorunk óta hozzászoktunk és amelyek világában ezért otthonosan mozgunk. Amennyiben tehát sikerül egy problématerületet geometriai kérdések összességére transzformálunk, úgy egyszerre lehetővé válik annak vizuális megjelenítése, elmagyarázása, új mentális modellek létrehozása és ezek segítségével a probléma mélyebb megértése. Amennyiben a pályázat témáját képező geometriai hálózatelmélet kidolgozása megtörténik, úgy számíthatunk tehát arra, hogy ez az elmélet fontos nyitott kérdések megválaszolásában lesz majd segítségünkre és használatával új, hatékonyabb algoritmusokat hozhatunk majd létre.
Fontos látni, hogy a javasolt kutatás felfedező kutatás. Mint ilyen, kimenete bizonytalan, ugyanakkor, a kutatási program sikeres végigvitele esetén hatalmas jelentőségű lehet. Meggyőződésem, hogy a hálózati geometria elmélete a hálózatmodellezés, -analízis és -optimalizálás új területeit nyithatja meg és új távközlési szabványok és nemzetközi szabadalmak alapja lehet. A kitűzött célok mind elméleti, mind pedig gyakorlati szempontból nagy jelentőségűek, amit talán az bizonyít a legjobban, hogy a területen korábban elért eredményeket a kommunikációs hálózatok vizsgálatával foglalkozó konferenciák közül az egyik legjelentősebb és legszelektívebb konferencián, az IEEE Infocom-on is elfogadták közlésre.
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.
Napjaink távközlési hálózatai új kihívásokkal néznek szembe, mivel új és új alkalmazások tűnnek fel nap mint nap mint az IPTV, VoIP, vagy az online játékok. A multimédia alkalmazások szigorú minőségi követelményeket támasztanak a hálózattal szemben, úgy mint a csomagok gyors és megbízható célba juttatása, magas rendelkezésre állás, alacsony csomagvesztés, stb. Sajnos azok az elméleti modellek, melyekre napjaink hálózatait építették, nem felelnek meg ezeknek a kritériumoknak. Addig, amíg egy megalapozott elméleti háttér nem áll a mérnökök és tudósok rendelkezésére, az Internet sohasem válhat olyan mindenhol jelen levő kritikus infrastruktúrává, melyen a jövő információs társadalmát megalapozhatjuk.
Az emberiség összes kritikus infrastruktúrája a gyakorlatban is jól használható elméletekre alapul. Elég csak például a villamosenergia-hálózat példáját venni, ahol a Maxwell-egyenletek és a származtatott távvezeték-egyenletek szinte minden tervezési és méretezési problémát megalapoznak. Az információs infrastruktúra, az Internet ma sajnos még nem rendelkezik hasonló elméleti megalapozottsággal. Sok versengő elmélet van, melyek a diszkrét matematika, a szabályozáselmélet, vagy a statisztikus mechanika területeiről merítenek, de egyik sem bizonyult még a hálózatok Nagy Egyesített Elméletének. Nem gondolom természetesen, hogy a pályázat alapját képező geometriai keretrendszer ilyen elméletnek bizonyul majd, de az meggyőződésem, hogy a fenti elméleti eszközök tárházának bővítése mindenképpen közelebb visz majd egy ilyen elméleti háttér kidolgozásához. Amennyiben ez bekövetkezik, úgy a következő generációs adathálózatok már ezekre az új alapokra építhetnek.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The aim of the present research proposal is to develop a novel geometric framework in order to provide deep insights into the elemental limitations and trade-offs involved in efficient and dependable network routing. I intend to uncover, in a very illustrative manner, how traffic instances compete for network resources and how users affect each other's traffic in a resource constrained network, and how to provision forwarding paths as to minimize the interference. The basic idea is to view networks and routing protocols in a completely new way, by assigning simple geometric objects to them and studying their interaction through observing the geometric properties thereof. This approach opens up a plethora of new possibilities in modeling, mathematical analysis, algorithm design, and numeric methods, as it augments the existing, fundamentally *algebraic* theoretical toolset, like the theory of network flows, linear programming, etc., with a new, inherently *geometric* point of view. This approach has already proved itself remarkably fruitful in answering some open questions in network theory, like for instance deciding whether a routing independent max-min fair resource allocation exists in every network. Consequently, it is my belief that, provided that the theoretical and practical underpinnings are worked out in full glory, the proposed framework for network geometry can give a uniquely capable tool in the hands of the networking community.
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.
The central hypothesis of the proposed research is that there exists an expressive and tangible geometric background behind some of the most elemental questions of network routing. I believe that, similarly to how geometry proved useful in abstract algebra or how differential geometry substantiated relativistic physics, network routing too can cover deep geometric concepts. This hypothesis is based on the observation I made in the course of previous research that there is a natural correspondence between a network and the traffic matrices that can be routed in it, and an associated geometric space and certain geometric objects, namely polyhedra, defined in this space. Every operation and transformation carried out on the network has a natural geometric counterpart, and I have found that often times the geometric interpretation suggests a much more descriptive and analyzable mental model than the flow theoretical one. The most important aim of the present grant proposal is to work out and understand the geometric framework in full detail, to develop the related analytical and numeric techniques, and to exploit these in order to answer some of the most compelling open questions of networking today.
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.
Sooner or later, some forms of geometry appears in basically any field of science. Based on my view, the reason for this is that geometry provides abstractions, in the form of spaces, points, lines, angles, geometric transformations, or the very axioms of geometry, that we have grown to use comfortably since infancy and which, therefore, give a very familiar mental environment to work in. Correspondingly, if one manages to translate a research field into a bunch of equivalent questions of geometry, then one obtains an extremely useful new way to visualize and reason about the related concepts, and hence a chance to get a deeper understanding of the underlying problems. Provided that the geometric theory that constitutes the subject of this proposal is worked out to a sufficient detail, we can reasonably expect that it helps answering important open questions and working out new, more efficient algorithms.
It is crucial to see that the proposed research is basic research. As such, the end results are uncertain, but can bring enormous benefits. I am confident that the proposed geometric framework can open up new areas of network modeling, analysis, and optimization, and can yield new telecommunications standards and international patents. The research goals are important both from a practical and a theoretical stand point, which is perhaps best demonstrated by the fact that my former research results in the field were accepted or publication at one of the most competitive and most selective top-notch research conferences in networking, IEEE Infocom.
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.
Modern networks face new challenges, as new applications, like IPTV, VoIP, online gaming, etc., now seem to appear every day. Most multimedia applications pose stringent requirements on transmission quality, like high availability, low traffic loss, etc. Unfortunately, the fundamental design principles today's networks were based upon are not adequate to meet these needs. Therefore, a mayor re-architecting of the Internet has become compelling, and such an undertaking needs a clear and well-established theoretical foundation. Until such a theory becomes available, the Internet will never evolve into the omni-present critical infrastructure onto which the upcoming information age can be founded.
Essentially every critical infrastructure of mankind is built on solid theoretical foundations. Think of the power transmission grid for instance. For this infrastructure, the Maxwell equations and the related power transmission line equations provide a solid theoretical underpinning for design, provisioning, and analysis. For telecommunications networks, however, no such theoretical foundation exists today. There are many competing theories on the table, based on discrete mathematics, control theory, or statistical mechanics, but so far non of these has become the Great Unified Theory of networking. Of course, I do not believe that the geometric theory proposed in this application will become this all-encompassing theory. But I do believe that working out this theory will definitely bring us closer to find such a theory. If this happens, then we can build next-generation data networks to a completely new foundation.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| G. Németh and G. Rétvári: Towards a statistical characterization of the competitiveness of oblivious routing (short paper), SIGMETRICS Perform. Eval. Rev., 40(1):387--388, 2012 | | Gábor Németh, Gábor Rétvári: Rate-adaptive multipath routing: Distributed, centralized, and hybrid architectures, Networks, 2015 | | A. Gulyás, J. J. Bíró, A. Kőrösi, G. Rétvári, and D. Krioukov: Navigable networks as Nash equilibria of navigation games, Nature Communications, 2015 | | G. Rétvári, D. Szabó, A. Gulyás, A. Kőrösi, and J. Tapolcai: An information-theoretic approach to routing scalability, ACM HotNets-XIII, pages 2:1--2:7, 2014 | | A. Kőrösi, J. Tapolcai, B. Mihálka, G. Mészáros, and G. Rétvári: Compressing IP forwarding tables: Realizing information-theoretical space bounds and fast lookups simultaneously, IEEE ICNP, 2014 | | G. Rétvári and J. Tapolcai and A. Kõrösi and A. Majdán and Z. Heszberger: Compressing IP Forwarding Tables: Towards Entropy Bounds and Beyond, Networking, IEEE/ACM Transactions on, 2014 | | Bence Mihálka, Attila Kőrösi, and Gábor Rétvári: Compressing virtual forwarding information bases using the trie-folding algorithm, Advances in Communication Networking, volume 8846 of Lecture Notes in Computer Science, pages 121--133, 2014 | | Csikor Levente; Rétvári Gábor: IP Fast Reroute with Remote Loop-Free Alternates: the Unit Link Cost Case, Proceedings of RNDM 2012, the 4th International Workshop on Reliable Networks Design and Modeling, 2012 | | Rétvári G.; Gulyás A., Heszberger Z., Csernai M., Bíró J.: Compact Policy Routing, Distributed Computing, 25:(6) pp. 1-12, 2012 | | Gábor Rétvári; Zoltán Csernátony; Attila Kőrösi; János Tapolcai; András Császár; Gábor Enyedi; Gergely Pongrácz: Compressing IP Routing Tables for Fun and Profit, 11th ACM Workshop on Hot Topics in Networks (HotNets-XI). Redmond, Amerikai Egyesült Államok, p. 1., 2012 | | Csikor Levente, Rétvári Gábor, Tapolcai János: High Availability in the Future Internet, Future Internet Architecture Book: Future Internet Assembly 2013: Validated Results and New Horizons. Berlin ; Heidelberg: Springer, pp. 64-76., 2013 | | Csikor Levente; Rétvári Gábor: On Providing Fast Protection with Remote Loop-Free Alternates: Analyzing and Optimizing Unit Cost Networks, Telecommunications Systems, 99:(1) pp. 1-16., 2013 | | L. Csikor; J. Tapolcai; G. Rétvári: Optimizing IGP Link Costs for Improving IP-level Resilience with Loop-Free Alternates, COMPUTER COMMUNICATIONS 36:(6) pp. 645-655., 2013 | | G Rétvári; J Tapolcai; A Kõrösi; A Majdán; Z Heszberger: Compressing IP Forwarding Tables: Towards Entropy Bounds and Beyond, ACM Sigcomm. Hong Kong, Kína, 2013 | | J Tapolcai; G Rétvári: Router Virtualization for Improving IP-level Resilience, IEEE Conference on Computer Communications (INFOCOM). Torino, Olaszország, pp. 935-943., 2013 | | Csikor Levente, Rétvári Gábor, Tapolcai János: High Availability in the Future Internet, Future Internet Architecture Book: Future Internet Assembly 2013: Validated Results and New Horizons. Berlin ; Heidelberg: Springer, pp. 64-76., 2013 | | L. Csikor; J. Tapolcai; G. Rétvári: Optimizing IGP Link Costs for Improving IP-level Resilience with Loop-Free Alternates, COMPUTER COMMUNICATIONS 36:(6) pp. 645-655., 2013 | | Gábor Németh, Gábor Rétvári: On the Competitiveness of Oblivious Routing: a Statistical View (accepted with revisions), Elsevier Performance Evaluation Review, 2014 | | Márton Zubor, Attila Kőrösi, András Gulyás, Gábor Rétvári: On the Computational Complexity of Policy Routing, 20th EUNICE Conference and Summer School (EUNICE 2014), Rennes, France, 2014 | | András Majdán, Gábor Rétvári, János Tapolcai: Development and Performance Evaluation of Fast Combinatorial Unranking Implementations, 20th EUNICE Conference and Summer School (EUNICE 2014), Rennes, France, 2014 | | Bence Mihálka, Attila Kőrösi, Gábor Rétvári: Compressing Virtual Forwarding Information Bases Using the Trie-folding Algorithm, 20th EUNICE Conference and Summer School (EUNICE 2014), Rennes, France, 2014 | | Krisztián Németh, Attila Kőrösi, Gábor Rétvári: Enriching the Poor Man’s Traffic Engineering: Virtual Link Provisioning for Optimal OSPF TE, 16th International Telecommunications Network Strategy and Planning Symposium (Networks 2014), Funchal, Madeira Island, Portugal, 2014 | | Attila Kőrösi, János Tapolcai, Bence Mihálka, Gábor Mészáros, Gábor Rétvári: Compressing IP Forwarding Tables: Realizing Information-theoretical Space Bounds and Fast Lookups Simultaneously, 22nd IEEE International Conference on Network Protocols (ICNP 2014), North Carolina, USA, 2014 | | András Gulyás, Gábor Rétvári, Zalán Heszberger, Rachit Agarwal: On the Scalability of Routing With Policies (accepted for publication), IEEE/ACM Transactions on Networking, 2014 | | G. Rétvári, J. Tapolcai, A. Kõrösi, A. Majdán, Z. Heszberger: Compressing IP Forwarding Tables: Towards Entropy Bounds and Beyond, revised manuscript (accepted for publication), EEE/ACM Transactions on Networking, 2014 |
|
|
|
|
|
|
|
|
|
