Sebastiano Miano, Alireza Sanaee, Fulvio Risso, Gábor Rétvári, and Gianni Antichi. Morpheus: A run time compiler and optimizer for software data planes. IEEE/ACM Transactions on Networking, (1):1--16, 2023. [ bib | paper [PDF] ]
Tamás Lévai, Balázs Kreith, and Gábor Rétvári. Supercharge WebRTC: Accelerate TURN services with eBPF/XDP. In Proceedings of the 1st Workshop on EBPF and Kernel Extensions, eBPF'23, pages 70--76, 2023. [ bib | DOI | paper [PDF] | http ]
Vamsi Addanki, Maciej Pacut, Arash Pourdamghani, Gabor Rétvári, Stefan Schmid, and Juan Vanerio. Self-adjusting partially ordered lists. In IEEE INFOCOM 2023-IEEE Conference on Computer Communications, pages 1--10. IEEE, 2023. [ bib | paper [PDF] ]
Péter Babarczi, Gábor Rétvári, Lajos Rónyai, and János Tapolcai. Routing on the shortest pairs of disjoint paths. In IFIP Networking Conference, pages 1--9. IFIP, 2022. [ bib | paper [PDF] ]
Balázs Vass, Csaba Sarkadi, and Gábor Rétvári. Programmable packet scheduling with SP-PIFO: Theory, algorithms and evaluation. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 1--6. IEEE, 2022. [ bib | paper [PDF] ]
Tamás Lévai and Gábor Rétvári. Batch-scheduling data flow graphs with service-level objectives on multicore systems. Infocommunications Journal, 14(1):43--50, 2022. [ bib | paper [PDF] ]
Sebastiano Miano, Alireza Sanaee, Fulvio Risso, Gábor Rétvári, and Gianni Antichi. Domain specific run time optimization for software data planes. In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2022, pages 1148--1164. Association for Computing Machinery, 2022. [ bib | DOI | paper [PDF] ]
Oliver Michel, Roberto Bifulco, Gábor Rétvári, and Stefan Schmid. The programmable data plane: Abstractions, architectures, algorithms, and applications. ACM Comput. Surv., 54(4), May 2021. [ bib | DOI | paper [PDF] ]
Marco Chiesa, Andrzej KamisiĹ„ski, Jacek Rak, Gábor Rétvári, and Stefan Schmid. A survey of fast-recovery mechanisms in packet-switched networks. IEEE Communications Surveys Tutorials, 23(2):1253--1301, 2021. [ bib | DOI | paper [PDF] ]
Ori Rottenstreich, Ariel Kulik, Ananya Joshi, Jennifer Rexford, Gábor Rétvári, and Daniel Menasché. Data plane cooperative caching with dependencies. IEEE Transactions on Network and Service Management, pages 1--1, 2021. [ bib | DOI | paper [PDF] ]
Ori Rottenstreich, Ariel Kulik, Ananya Joshi, Jennifer Rexford, Gábor Rétvári, and Daniel S. Menasché. Cooperative rule caching for SDN switches. In 2020 IEEE 9th International Conference on Cloud Networking (CloudNet), pages 1--7, 2020. [ bib | DOI | paper [PDF] ]
Gábor Rétvári. L7mp: A multiprotocol service mesh for legacy applications. ServiceMeshCon NA 2020, colocated with KubeCon + CloudNativeCon North America, 2020. video available at https://www.youtube.com/watch?v=4oTP91yfF3g. [ bib | slides [PDF] | http ]
Levente Csikor, Márk Szalay, Gábor Rétvári, Gergely Pongrácz, Dimitrios P Pezaros, and László Toka. Transition to SDN is HARMLESS: Hybrid architecture for migrating legacy ethernet switches to SDN. IEEE/ACM Transactions on Networking, 28(1):275--288, 2020. [ bib ]
András Gulyás, József Bíró, Gábor Rétvári, Márton Novák, Attila Kőrösi, Mariann Slíz, and Zalán Heszberger. The role of detours in individual human navigation patterns of complex networks. Scientific reports, 10(1):1--10, 2020. [ bib | paper [PDF] ]
Balázs Vass, Erika Bérczi-Kovács, Costin Raiciu, and Gábor Rétvári. Compiling packet programs to reconfigurable switches: Theory and algorithms. In Proceedings of the 3rd P4 Workshop in Europe, EuroP4'20, pages 28--35, New York, NY, USA, 2020. Association for Computing Machinery. [ bib | DOI | slides [PDF] | paper [PDF] | http ]
G. Antichi and G. Rétvári. Full-stack SDN: The next big challenge? In Proceedings of the Symposium on SDN Research, SOSR ’20, page 48–54, New York, NY, USA, 2020. Association for Computing Machinery. [ bib | DOI | slides [PDF] | paper [PDF] | http ]
T. Lévai, F. Németh, B. Raghavan, and G. Rétvári. Batchy: Batch-scheduling data flow graphs with service-level objectives. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 633--649, Santa Clara, CA, 2020. USENIX Association. [ bib | paper [PDF] | http ]
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, pages 1--11, 2020. [ bib | DOI | paper [PDF] ]
Kashyap Thimmaraju, Saad Hermak, Gábor Rétvári, and Stefan Schmid. MTS: Bringing multi-tenancy to virtual networking. In 2019 USENIX Annual Technical Conference (USENIX ATC 19), pages 521--536, Renton, WA, July 2019. USENIX Association. [ bib | slides [PDF] | paper [PDF] ]
J. Tapolcai, G. Rétvári, P. Babarczi, and E. R. Bérczi-Kovács. Scalable and efficient multipath routing via redundant trees. IEEE Journal on Selected Areas in Communications, 37(5):982--996, May 2019. [ bib | DOI | paper [PDF] ]
M. Nagy, J. Tapolcai, and G. Rétvári. R3D3: A doubly opportunistic data structure for compressing and indexing massive data. Infocommunications Journal, 11(2):58--66, January 2019. [ bib | paper [PDF] ]
Johannes Zerwas, Patrick Kalmbach, Laurenz Henkel, Gábor Rétvári, Wolfgang Kellerer, Andreas Blenk, and Stefan Schmid. Netboa: Self-driving network benchmarking. In Proceedings of the 2019 Workshop on Network Meets AI & ML, page 8–14, 2019. [ bib | DOI ]
A. Kőrösi and G. Rétvári. A csomagtovábbítás skálázhatósága: korlátok és optimumok. ALKALMAZOTT MATEMATIKAI LAPOK, 36, 2019. [ bib | paper [PDF] ]
J. Bíró, A. Gulyás, G. Rétvári, A. Kőrösi, Z. Heszberger, and A. Majdán. Navigáció hálózatokban Bolyai János geometriája segítségével. ALKALMAZOTT MATEMATIKAI LAPOK, 36, 2019. [ bib ]
F. Németh, M. Chiesa, and G. Rétvári. Normal forms for match-action programs. In ACM CoNEXT, pages 44--50, 2019. [ bib | DOI | paper [PDF] ]
L. Csikor, D.M. Divakaran, M.S. Kang, A. Kőrösi, B. Sonkoly, D. Haja, D. Pezaros, S. Schmid, and G. Rétvári. Tuple space explosion: A denial-of-service attack against a software packet classifier. In ACM CoNEXT, pages 292--304, 2019. [ bib | DOI | paper [PDF] ]
L. Linguaglossa, S. Lange, S. Pontarelli, G. Rétvári, D. Rossi, T. Zinner, R. Bifulco, M. Jarschel, and G. Bianchi. Survey of performance acceleration techniques for Network Function Virtualization. Proceedings of the IEEE, 107(4):746--764, 2019. [ bib | DOI | paper [PDF] ]
T. Lévai, G. Pongrácz, P. Megyesi, P. Vörös, S. Laki, F. Németh, and G. Rétvári. The price for programmability in the software data plane: The vendor perspective. IEEE Journal on Selected Areas in Communications, 36(12):2621--2630, December 2018. [ bib | DOI | paper [PDF] ]
Marco Chiesa, Gabor Retvari, and Michael Schapira. Oblivious routing in IP networks. IEEE/ACM Transactions on Networking, 26(3):1292--1305, June 2018. [ bib | DOI | paper [PDF] ]
Máté Nagy, János Tápolcai, and Gábor Rétvári. Node virtualization for IP level resilience. IEEE/ACM Transactions of Networking, 26(3):1250--1263, June 2018. [ bib | DOI | paper [PDF] ]
K. Thimmaraju, G. Rétvári, and S. Schmid. Virtual network isolation: Are we there yet? In Proc. ACM SIGCOMM 2018 Workshop on Security in Softwarized Networks: Prospects and Challenges (SecSon), 2018. [ bib ]
Roberto Bifulco and Gábor Rétvári. A survey on the programmable data plane: Abstractions architectures and open problems. In Proc. IEEE HPSR, 2018. [ bib | paper [PDF] ]
Levente Csikor, László Toka, Márk Szalay, Gergely Pongrácz, Dimitrios P Pezaros, and Gábor Rétvári. Harmless: Cost-effective transitioning to SDN for small enterprises. In Proc. IFIP Netw., pages 1--9, 2018. [ bib | paper [PDF] ]
Attila Kőrösi, Attila Csoma, Gábor Rétvári, Zalán Heszberger, József Bíró, János Tapolcai, István Pelle, Dávid Klajbár, Márton Novák, Valentina Halasi, et al. A dataset on human navigation strategies in foreign networked systems. Scientific data, 5:180037, 2018. [ bib | paper [PDF] ]
A. Csoma, A. Kőrösi, G. Rétvári, Z. Heszberger, J. J. Bíró, M. Slíz, A. Avena-Koenigsberger, A. Griffa, P. Hagmann, and A. Gulyás. Routes obey hierarchy in complex networks. Nature Scientific Reports, 7, 2017. [ bib | paper [PDF] ]
G. Rétvári, L. Molnár, G. Pongrácz, and G. Enyedi. Dynamic compilation and optimization of packet processing programs. In ACM SIGCOMM 2017 The Third Workshop on Networking and Programming Languages (NetPL), 2017. [ bib | slides [PDF] | paper [PDF] ]
K. Németh, A. Körösi, and G. Rétvári. Optimal resource pooling over legacy equal-split load balancing schemes. Computer Networks, 127:243--265, 2017. [ bib | DOI | paper [PDF] ]
Abstract Splitting traffic flows to different data paths is crucial in current and future networks. Traffic division serves as the basis for load balancing between application servers, optimal Traffic Engineering, using multiple paths in data centers, and several other places of an end-to-end connection. Unfortunately, by allowing only equal division amongst the parallel resources, existing technologies often cannot realize the optimal traffic splitting, which can have serious negative consequences on the network performance. In this paper we present a flexible and effective traffic splitting method that is incrementally deployable and fully compatible with practically all existing protocols and data planes. Our proposal, called Virtual Resource Allocation (VRA), is based on setting up virtual resources alongside existing ones, thereby tricking the legacy equal traffic splitting technology into realizing the required non-equal traffic division over the physical media. We propose several {VRA} schemes, give theoretical bounds on their performance, and also show that the full-fledged {VRA} problem is NP-complete in general. Accordingly, we provide solution algorithms, including an optimal, but necessarily slow method and several quick heuristics. Our simulations show that {VRA} has huge practical potential as it allows approaching an ideal traffic split using only a very limited set of virtual resources. Based on the results, we also give detailed suggestions on which algorithm to apply in different scenarios.
S. Nikolenko, K. Kogan, G. Rétvári, E. Bérczi-Kovács, and A. Shalimov. How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes. In Proc. 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS): GI 2016: 19th IEEE Global Internet Symposium, 2016. [ bib | paper [PDF] ]
L. Molnár, G. Pongrácz, G. Enyedi, Z. L. Kis, L. Csikor, F. Juhász, A. Kőrösi, and G. Rétvári. Dataplane specialization for high performance OpenFlow software switching. In ACM SIGCOMM, pages 539--552, 2016. [ bib | DOI | slides [PDF] | paper [PDF] ]
M. Chiesa, G. Rétvári, and M. Schapira. Lying your way to better traffic engineering. In ACM CoNEXT, pages 391--398, 2016. [ bib | DOI | paper [PDF] ]
G. Rétvári, J. Tapolcai, A. Kőrösi, A. Majdán, and Z. Heszberger. Compressing IP forwarding tables: Towards entropy bounds and beyond. IEEE/ACM Transactions on Networking, 24(1):149--162, 2016. [ bib | DOI | paper [PDF] ]
Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state of the art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we redesign the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode an FIB comprising more than 440 K prefixes to just about 100-400 kB of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.
András Gulyás, Gábor Rétvári, Zalán Heszberger, and Rachit Agarwal. On the scalability of routing with policies. IEEE/ACM Transactions on Networking, 23(5):1610--1618, October 2015. [ bib | DOI | paper [PDF] ]
Today's ever-growing networks call for routing schemes with sound theoretical scalability guarantees. In this context, a routing scheme is scalable if the amount of memory needed to implement it grows significantly slower than the network size. Unfortunately, theoretical scalability characterizations only exist for shortest path routing, but for general policy routing that current and future networks increasingly rely on, very little understanding is available. In this paper, we attempt to fill this gap. We define a general framework for policy routing, and we study the theoretical scaling properties of three fundamental policy models within this framework. Our most important contributions are the finding that, contrary to shortest path routing, there exist policies that inherently scale well, and a separation between the class of policies that admit compact routing tables and those that do not. Finally, we ask to what extent memory size can be decreased by allowing paths to contain a certain bounded number of policy violations and, surprisingly, we conclude that most unscalable policies remain unscalable under the relaxed model as well.
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, 6(7651), July 2015. [ bib | DOI | paper [PDF] ]
L. Csikor and G. Rétvári. On providing fast protection with remote loop-free alternates -- analyzing and optimizing unit cost networks. Telecommunication Systems Journal, March 2015. [ bib | DOI | paper [PDF] ]
J. Tapolcai, G. Rétvári, P. Babarczi, E. Bérczi-Kovács, P. Kristóf, and G. Enyedi. Scalable and efficient multipath routing: Complexity and algorithms. In 23rd IEEE International Conference on Network Protocols (ICNP), pages 1--10, San Francisco, CA, USA, 2015. [ bib | paper [PDF] ]
G. Németh and G. Rétvári. Rate-adaptive multipath routing: Distributed, centralized, and hybrid architectures. Networks, pages 1--12, 2015. [ bib | DOI | paper [PDF] ]
Márton Zubor, Attila Korösi, András Gulyás, and Gábor Rétvári. On the computational complexity of policy routing. In Yvon Kermarrec, editor, Advances in Communication Networking, volume 8846 of Lecture Notes in Computer Science, pages 202--214. Springer International Publishing, 2014. [ bib | DOI | paper [PDF] ]
Bence Mihálka, Attila Kőrösi, and Gábor Rétvári. Compressing virtual forwarding information bases using the trie-folding algorithm. In Yvon Kermarrec, editor, Advances in Communication Networking, volume 8846 of Lecture Notes in Computer Science, pages 121--133. Springer International Publishing, 2014. [ bib | DOI ]
A. Majdán, G. Rétvári, J. Tapolcai, and A. Kőrösi. Development and performance evaluation of fast combinatorial unranking implementations. In IFIP EUNICE, Rennes, France, 2014. [ bib ]
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. In Proc. IEEE ICNP, 2014. [ bib | paper [PDF] ]
G. Rétvári, D. Szabó, A. Gulyás, A. Kőrösi, and J. Tapolcai. An information-theoretic approach to routing scalability. In ACM HotNets-XIII, pages 1--7, 2014. [ bib | DOI | slides [PDF] | paper [PDF] ]
J. Tapolcai and G. Rétvári. Router virtualization for improving IP-level resilience. In IEEE INFOCOM, pages 935--943, April 2013. [ bib | DOI | slides [PDF] | paper [PDF] ]
G. Rétvári, J. Tapolcai, A. Kőrösi, A. Majdán, and Z. Heszberger. Compressing IP forwarding tables: Towards entropy bounds and beyond. In ACM SIGCOMM, pages 111--122, 2013. [ bib | DOI | slides [PDF] | paper [PDF] ]
K. Németh, A. Körösi, and G. Rétvári. Optimal OSPF traffic engineering using legacy Equal Cost Multipath load balancing. In IFIP Networking Conference 2013, pages 1--9, 2013. [ bib ]
L. Csikor, G. Rétvári, and J. Tapolcai. High availability in the Future Internet. In Alex Galis and Anastasius Gavras, editors, The Future Internet, volume 7858 of Lecture Notes in Computer Science, pages 64--76. Springer Berlin Heidelberg, 2013. [ bib | DOI | paper [PDF] ]
G. Rétvári, A. Gulyás, Z. Heszberger, M. Csernai, and J.J. Bíró. Compact policy routing. Distributed Computing, 26(5):309--320, 2013. [ bib | DOI | paper [PDF] ]
The main concern in this paper is to generalize compact routing to arbitrary routing policies that favor a broader set of path attributes beyond path length. Using the formalism of routing algebras we identify the algebraic requirements for a routing policy to be realizable with sublinear size routing tables, and we show that a wealth of practical policies can be classified by our results. By generalizing the notion of stretch, we also discover the algebraic validity of compact routing schemes considered so far and we show that there are routing policies for which one cannot expect sublinear scaling even if permitting arbitrary constant stretch. Finally, we apply our methodology to the routing policies used in Internet inter-domain routing, and we show that our algebraic approach readily generalizes to this setting as well.
K. Németh and G. Rétvári. Traffic splitting algorithms in multipath networks: Is the present practice good enough? In the 15th International Telecommunications Network Strategy and Planning Symposium, (Networks 2012), October 2012. [ bib ]
G. Rétvári, Z. Csernátony, A. Kőrösi, J. Tapolcai, A. Császár, G. Enyedi, and G. Pongrácz. Compressing IP forwarding tables for fun and profit. In ACM HotNets-XI. ACM, October 2012. [ bib | slides [PDF] | paper [PDF] ]
About what is the smallest size we can compress an IP Forwarding Information Base (FIB) down to, while still guaranteeing fast lookup? Is there some notion of FIB entropy that could serve as a compressibility metric? As an initial step in answering these questions, we present a FIB data structure, called Multibit Burrows-Wheeler transform (MBW), that is fundamentally pointerless, can be built in linear time, guarantees theoretically optimal longest prefix match, and compresses to higher-order entropy. Measurements on a Linux prototype provide a first glimpse of the applicability of MBW.
L. Csikor and G. Rétvári. IP Fast Reroute with Remote Loop-Free Alternates: The unit link cost case. In Proceedings of RNDM 2012, the 4th International Workshop on Reliable Networks Design and Modeling, pages 16--22, October 2012. [ bib | paper [PDF] ]
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, June 2012. [ bib | DOI | paper [PDF] ]
L. Csikor, J. Tapolcai, and G. Rétvári. Optimizing IGP link costs for improving IP-level resilience with Loop-Free Alternates. Computer Communications, 2012. [ bib | DOI | paper [PDF] ]
The IP Fast ReRoute-Loop-Free Alternates (LFA) standard is a simple and easily deployable technique to provide fast failure protection right in the IP layer. To our days, most major IP device vendors have products on the market that support LFA out of the box. Unfortunately, LFA usually cannot protect all possible failure scenarios in a general network topology. Therefore, it is crucial to develop LFA-based network optimization tools in order to assist operators in deciding whether deploying LFA in their network will supply sufficient resiliency. In this paper, we give a new graph theoretical framework for analyzing LFA failure case coverage, and then we investigate how to optimize the Interior Gateway Protocol (IGP) link costs in order to maximize the number of protected failure scenarios. We show that this problem is NP-complete even in a very restricted formulation, and we give an exact algorithm as well as a complete family of heuristics to solve it. Our simulation studies indicate that a deliberate tuning of the approximation strategy can significantly improve the quality of the IGP link costs, and we conclude that LFA cost optimization has the potential for boosting LFA-based resilience in most operational networks significantly.
M. Nagy, J. Tapolcai, and G. Rétvári. Optimization methods for improving IP-level fast protection for local Shared Risk Groups with Loop-Free Alternates. Telecommunication Systems, 2012. [ bib | paper [PDF] ]
Cs. Simon, F. Németh, F. Uzsák, G. Rétvári, F. Ficsor, and R. Vida. Autonomic DHCPv6 architecture. In GLOBECOM Workshops, 2011 IEEE, pages 620--624, December 2011. [ bib | DOI ]
M. Nagy and G. Rétvári. An evaluation of approximate network optimization methods for improving IP-level fast protection with Loop-free Alternates. In Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2011 3rd International Congress on, pages 1--7, October 2011. [ bib | paper [PDF] ]
G. Rétvári, L. Csikor, J. Tapolcai, G. Enyedi, and A. Császár. Optimizing IGP link costs for improving IP-level resilience (best paper award). In Design of Reliable Communication Networks (DRCN), 2011 8th International Workshop on the, pages 62--69, October 2011. [ bib | DOI | slides [PDF] | paper [PDF] ]
Recently, major vendors have introduced new router platforms to the market that support fast IP-level failure protection out of the box. The implementations are based on the IP Fast ReRoute-Loop Free Alternates (LFA) standard. LFA is simple, unobtrusive, and easily deployable. This simplicity, however, comes at a severe price, in that LFA usually cannot protect all possible failure scenarios. In this paper, we give new graph theoretical tools for analyzing LFA failure case coverage and we seek ways for improvement. In particular, we investigate how to optimize IGP link costs to maximize the number of protected failure scenarios, we show that this problem is NP-complete even in a very restricted formulation, and we give exact and approximate algorithms to solve it. Our simulation studies show that a deliberate selection of IGP costs can bring many networks close to complete LFA-based protection.
G. Rétvári, A. Gulyás, Z. Heszberger, M. Csernai, and J.J. Bíró. Compact policy routing. In ACM PODC 2011, pages 149--158, New York, NY, USA, 2011. ACM. [ bib | DOI | slides [PDF] | paper [PDF] ]
This paper takes a first step towards generalizing compact routing to arbitrary routing policies that favor a broader set of path attributes beyond path length. Using the formalism of routing algebras we identify the algebraic requirements for a routing policy to be realizable with sublinear size routing tables and we show that a wealth of practical policies can be classified by our results. By generalizing the notion of stretch, we also discover the algebraic validity of compact routing schemes considered so far and we show that there are routing policies for which one cannot expect sublinear scaling even if permitting arbitrary constant stretch.
G. Rétvári, J. Tapolcai, G. Enyedi, and A. Császár. IP Fast ReRoute: Loop Free Alternates revisited. In IEEE INFOCOM 2011, pages 2948--2956, 2011. [ bib | DOI | slides [PDF] | paper [PDF] ]
IP Fast ReRoute (IPFRR) is the IETF standard for providing fast failure protection in IP and MPLS/LDP networks and Loop Free Alternates (LFA) is a basic specification for implementing it. Even though LFA is simple and unobtrusive, it has a significant drawback: it does not guarantee protection for all possible failure cases. Consequently, many IPFRR proposals have appeared lately, promising full failure coverage at the price of added complexity and non-trivial modifications to IP hardware and software. Meanwhile, LFA remains the only commercially available, and therefore, the only deployable IPFRR solution. Deployment, however, crucially depends on the extent to which LFA can protect failures in operational networks. In this paper, therefore, we revisit LFA in order to give theoretical insights and practical hints to LFA failure coverage analysis. First, we identify the topological properties a network must possess to profit from good failure coverage. Then, we study how coverage varies as new links are added to a network, we show how to do this optimally and, through extensive simulations, we arrive to the conclusion that cleverly adding just a couple of new links can improve the quality of LFA protection drastically.
G. Rétvári, F. Németh, I. Hokelek, M. Fecko, A. Prakash, R. Chaparadza, M. Wodzak, and B. Vidalenc. A guideline for realizing the vision on Autonomic Networking: Implementing self-adaptive routing on top of OSPF. In Phan Cong-vinh, editor, Formal and Practical Aspects of Autonomic Computing and Networking: Specification, Development, and Verification. Information Science Reference - Imprint of: IGI Publishing, Hershey, PA, 1st edition, 2011. [ bib ]
M. Csernai, A. Gulyás, G. Rétvári, Z. Heszberger, and A. Császár. The skeleton of the internet. In IEEE GLOBECOM, pages 1--5, November 2010. [ bib | DOI | paper [PDF] ]
Research works concerning AS (Autonomous Systems) level Internet topology measurements typically aim at obtaining near-complete maps of the AS structure. In this paper, we take a fundamentally different approach by inspecting several concurrently visible local views of the AS graph stored at individual BGP route servers. We find that each of these views exhibits the characteristic properties of complex graphs having power-law degree distribution, large clustering coefficient and the small world property. As a main contribution, the intersection of these views is investigated to identify the skeleton of the Internet consisting of edges seen by most of the ASes. Our measurements support the surprising claim that this skeleton is a scale-free complex network, having a giant connected component with a dense part in its heart forming the critical AS level core. We identify the edges in the skeleton as critical infrastructure, any changes of which induces an Internet-wide effect with BGP updates propagating to all ASes. Finally, we reinterpret the path inflation metric using the local view approach and show that local path inflation can be very diverse in different ASes.
G. Rétvári and G. Németh. On optimal multipath rate-adaptive routing. In 15th IEEE Symposium on Computers and Communications (ISCC 2010), Riccione, Italy, June 2010. [ bib | DOI | paper [PDF] ]
A centralized rate-adaptive routing algorithm is presented that, in contrast to the distributed ones available in the literature, achieves provable stability, optimalilty with respect to optional linear or quadratic objective functions, and feasibility in that it can accommodate any admissible traffic matrix in the network without violating link capacities. We recast the routing problem in the framework of constrained optimal control theory to obtain optimal state feedback routing controllers, and we present simulations confirming that our routing controllers are viable in small- and middle-sized networks.
G. Rétvári and G. Németh. Demand-oblivious routing: Distributed vs. centralized approaches. In IEEE INFOCOM 2010, March 2010. [ bib | DOI | slides [PDF] | paper [PDF] ]
Until recent years, it was more or less undisputed common-sense that an accurate view on traffic demands is indispensable for optimizing the flow of traffic through a network. Lately, this premise has been questioned sharply: it was shown that setting just a single routing, the so called demand-oblivious routing, is sufficient to accommodate any admissible traffic matrix in the network with moderate link overload, so no prior information on demands is absolutely necessary for efficient traffic engineering. Demand-oblivious routing lends itself to distributed implementations, so it scales well. In this paper, we generalize demand-oblivious routing in a new way: we show that, in contrast to the distributed case, centralized demand-oblivious routing can eliminate link overload completely. What is more, our centralized scheme allows for optimizing the routes with respect to arbitrary linear or quadratic objective function. We realize, however, that a centralized scheme can become prohibitively complex, therefore, we propose a hybrid distributed-centralized algorithm, which, according to our simulations, strikes a good balance between efficiency, scalability and complexity.
G. Enyedi and G. Rétvári. Finding multiple maximally redundant trees in linear time. Periodica Polytechnica, 54:29--40, 2010. [ bib | DOI | paper [PDF] ]
Redundant trees are directed spanning trees, which provide disjoint paths towards their roots. Therefore, this concept is widely applied in the literature both for providing protection and load sharing. The fastest algorithm can find multiple redundant trees, a pair of them rooted at each vertex, in linear time. Unfortunately, edge- or vertex-redundant trees can only be found in 2-edge- or 2-vertex-connected graphs respectively. Therefore, the concept of maximally redundant trees was introduced, which can overcome this problem, and provides maximally disjoint paths towards the common root. In this paper, we propose the first linear time algorithm, which can compute a pair of maximally redundant trees rooted at not only one, but at each vertex.
G. Németh and G. Rétvári. Hybrid demand oblivious routing: Hyper-cubic partitions and theoretical upper bounds. In 7th International ICST Conference on Broadband Communications, Networks, and Systems (BROADNETS 2010), pages 25--27, 2010. [ bib | DOI | paper [PDF] ]
G. Rétvári, F. Németh, C. Ranganai, and R. Szabó. OSPF for implementing self-adaptive routing in autonomic networks: A case study. In MACE'09, the 4th International Workshop on Modelling Autonomic Communications Environments, October 2009. [ bib | DOI | paper [PDF] ]
Autonomicity, realized through control-loop structures operating within network devices and the network as a whole, is an enabler for advanced and enriched self-manageability of network devices and networks. In this paper, we argue that the degree of self-management and self-adaptation embedded by design into existing protocols needs to be well understood before one can enhance or integrate such protocols into self-managing network architectures that exhibit more advanced autonomic behaviors. We justify this claim through an illustrative case study: we show that the well-known and extensively used intra-domain IP routing protocol, OSPF, is itself a quite capable self-managing entity, complete with all the basic components of an autonomic networking element like embedded control-loops, decision-making modules, distributed knowledge repositories, etc. We describe these components in detail, concentrating on the numerous control-loops inherent to OSPF, and discuss how some of the control-loops can be enriched with external decision making logics to implement a truly self-adapting routing functionality.
F. Németh, G. Rétvári, Z. Heszberber, and A. Gulyás. Demystifying self-awareness of autonomic systems. In Proc., ICT Mobile and Wireless Communications Summit (MobileSummit), Santander, Spain, June 2009. [ bib ]
Self-awareness is a much discussed property of autonomic and self-managed networks. Attempting to demystify this property we show that it can be captured by a Self Awareness Function (SAF) that stems from the assessment of process correctness of autonomic and cognitive networks. Based on multiple position papers that were written in isolation we are able to identify various SAFs (for trust, security, dynamics control, service deployment), as well as associated research issues (information modelling, higher contextualisation, convergence, etc.). We show that multiple issues of self -management that create a tangled hierarchy of control loops can be systematically addressed with SAF in mind.
G. Rétvári. The geometry of networking, part II. In Proceedings of High Speed Networking 2009 Spring Workshop, Balatonkenese, Hungary, May 2009. [ bib ]
G. Enyedi, G. Rétvári, and A Császár. On finding maximally redundant trees in strictly linear time. In IEEE Symposium on Computers and Communications (ISCC 2009), pages 206--211, Tunesia, 2009. [ bib | DOI | paper [PDF] ]
Redundant trees are commonly used for protection and restoration in communications networks. Zhang et al. presented a linear time algorithm to compute node-redundant trees in 2-node-connected networks, which has become widely cited in the literature. In this paper, we show that it is difficult to implement this algorithm providing both correctness and linear complexity at the same time. Therefore, we present a revised algorithm with strict linear time complexity. Moreover, we generalize the concept of node-redundant trees from 2-node-connected networks to arbitrary topologies, a crucial development since real networks can not always satisfy 2-connectedness, especially after a failure.
G. Enyedi, P. Szilágyi, G. Rétvári, and A Császár. IP fast reroute: Lightweight Not-Via without additional addresses. In IEEE INFOCOM'09 Mini-Conference, pages 2771--2775, Rio de Janeiro, Brasil, 2009. [ bib | DOI | paper [PDF] ]
In order for IP to become a full-fledged carrier-grade transport technology, a native IP failure-recovery scheme is necessary that can correct failures in the order of milliseconds. IP fast reroute (IPFRR) intends to fill this gap, providing fast, local and proactive handling of failures right in the IP layer. Building on experiences and extensive measurement results collected with a prototype implementation of the prevailing IPFRR technique, Not-via, in this paper we identify high address management burden and computational complexity as the major causes of why commercial IPFRR deployment still lags behind, and we present a lightweight not-via scheme, which, according to our measurements, improves these issues.
G. Enyedi, P. Szilágyi, G. Rétvári, and A Császár. IP fast reroute: Lightweight Not-Via. In Lecture Notes in Computer Science: Proceedings of the IFIP Networking'09, pages 157--168, Aachen, Germany, 2009. [ bib | DOI | paper [PDF] ]
In order for IP to become a full-fledged carrier-grade transport technology, a native IP failure-recovery scheme is necessary that can correct failures in the order of milliseconds. IP Fast ReRoute (IPFRR) intends to fill this gap, providing fast, local and proactive handling of failures right in the IP layer. Building on experiences and extensive measurement results collected with a prototype implementation of the prevailing IPFRR technique, Not-via, in this paper we identify high address management burden and computational complexity as the major causes of why commercial IPFRR deployment still lags behind, and we present a lightweight Not-via scheme, which, according to our measurements, improves these issues.
G. Enyedi and G. Rétvári. Gyors hibajavítás IP hálózatokban (in hungarian). Híradástechnika, 64:20--24, 2009. [ bib | paper [PDF] ]
P. Fodor, G. Enyedi, G. Rétvári, and T. Cinkler. Layer-preference policies in multi-layer GMPLS networks. Photonic Network Communications, 18:300--313, 2009. [ bib | DOI | paper [PDF] ]
We address the problem of routing Label Switched Paths (LSPs) in multi-layer networks based on the Generalized MultiProtocol Label Switching (GMPLS) paradigm. In particular, we pursue policies for choosing the appropriate layer to host a new LSP request, as we find that such layer-preference policies have significant impact on network performance. We discuss several simple layer-preference policies and we reveal why these simple policies ruin network performance in the long run. Consequently, we develop an efficient heuristics, the Min-phys-hop routing and wavelength assignment algorithm, to govern the selection of the best layer of a multi-layer network in which to host new LSP requests. We discuss the applicability of this algorithm with respect to the state-of-the-art GMPLS standards, above all, the GMPLS routing extensions to OSPF-TE. By extensive simulations, we justify that the Min-phys-hop algorithm produces close-to-optimal blocking and resource consumption under almost all possible selections of input parameters, and this is regardless of the wavelength and Optical-Electrical-Optical (OEO) conversion capability present in the network.
P. Fodor, G. Enyedi, G. Rétvári, and T. Cinkler. An efficient and practical layer-preference policy for routing in GMPLS networks. In the 13th International Telecommunications Network Strategy and Planning Symposium, (Networks 2008), September 2008. [ bib | DOI | paper [PDF] ]
We address the problem of routing Label Switched Paths (LSPs) in multi-layer networks based on the Generalized MultiProtocol Label Switching (GMPLS) paradigm. In particular, we pursue strategies for choosing the appropriate layer to host a new LSP request, since choosing this policy has enormous impact on the eventual performance of the network. Therefore, we developed a mixed strategy, the Min-phys-hop routing and wavelength assignment algorithm, as a policy to govern the selection of the best layer of a multi-layer network in which to host new LSP requests. In this paper, we discuss the practical issues concerning the deployment of this algorithm in modern GMPLS networks. Firstly, we discuss the applicability of the algorithm with respect to the state-of-the-art GMPLS standards, above all, the GMPLS routing extensions to OSPF-TE. We also sketch two possible reference deployment scenarios. Secondly, we present simulation studies to demonstrate that (1) there does not exist a universally optimal static layer-preference policy and (2) the Min-phys-hop algorithm realizes an adequate heuristics even considering the realistic limitations of contemporary network devices. We found that the Min-phys-hop algorithm produces close-to-optimal blocking and resource consumption under almost all possible selections of input parameters, and this is regardless of the wavelength and Optical-Electrical-Optical (OEO) conversion capability present in the network.
G. Enyedi and G. Rétvári. A loop-free interface-based fast reroute technique. In Next Generation Internet Networks, 2008. NGI 2008, pages 39--44, April 2008. [ bib | DOI ]
G. Rétvári, J. J. Bíró, and T. Cinkler. On shortest path representation. IEEE/ACM Transactions on Networking, 15(6):1293--1306, December 2007. [ bib | DOI | paper [PDF] ]
Lately, it has been proposed to use shortest path first routing to implement Traffic Engineering in IP networks. The idea is to set the link weights so that the shortest paths, and the traffic thereof, follow the paths designated by the operator. Clearly, only certain shortest path representable path sets can be used in this setting, that is, paths which become shortest paths over some appropriately chosen positive, integer-valued link weights. Our main objective in this paper is to distill and unify the theory of shortest path representability under the umbrella of a novel flow-theoretic framework. In the first part of the paper, we introduce our framework and state a descriptive necessary and sufficient condition to characterize shortest path representable paths. Unfortunately, traditional methods to calculate the corresponding link weights usually produce a bunch of superfluous shortest paths, often leading to congestion along the unconsidered paths. Thus, the second part of the paper is devoted to reducing the number of paths in a representation to the bare minimum. To the best of our knowledge, this is the first time that an algorithm is proposed, which is not only able to find a minimal representation in polynomial time, but also assures link weight integrality. Moreover, we give a necessary and sufficient condition to the existence of a one-to-one mapping between a path set and its shortest path representation. However, as revealed by our simulation studies, this condition seems overly restrictive and instead, minimal representations prove much more beneficial.
A. Császár, G. Enyedi, M. Hidell, G. Rétvári, and P. Sjödin. Converging the evolution of router architectures and IP networks. IEEE Network Magazine, Special Issue on Advances in Network Systems Architecture, 21(4):8--14, July 2007. [ bib | DOI | paper [PDF] ]
Although IP is widely recognized as the platform for next-generation converged networks, it is, unfortunately, heavily burdened by its heritage of almost 30 years. Nowadays, network operators must devote significant resources to carry out tasks so essential like traffic engineering, policy enforcement and security. In this paper, we argue that one of the principal reasons for this lies in the way control and forwarding planes are interspersed in today's IP networks. We review the architectural developments that led to the present situation and we reason that centralization of network control functionality can constitute a solution to the pressing problems of contemporary Internet.
G. Enyedi, G. Rétvári, and T. Cinkler. A novel loop-free IP Fast Reroute algorithm. In Proc., 13th EUNICE Open European Summer School, July 2007. [ bib | DOI ]
Although providing reliable network services is getting more and more important, currently used methods in IP networks are typically reactive and error correcting can take a long time. One of the most interesting solutions is interface based fast rerouting, where not only the destination address but also the incoming interface is taken into account during the forwarding. Unfortunately, current methods can not handle all the possible situations as they are prone to form loops and make parts of the network with no failure unavailable. In this paper we propose a new interface based routing method, which always avoids loops for the price of a bit longer paths. We also present extensive simulation results to compare current and proposed algorithms.
G. Rétvári, J. J. Bíró, and T. Cinkler. Routing-independent fairness in capacitated networks. In Proc., IEEE International Conference on Communications (ICC 2007), Glasgow, Scotland, June 2007. [ bib | DOI | paper [PDF] ]
The problem of fair and feasible allocation of user throughputs in capacitated networks is investigated. The main contribution of the paper is an extension of network fairness, and in particular, max-min fairness from the traditional fixed- path model to a more versatile, routing-independent model. We show that the set of throughput configurations realizable in a capacitated network makes up a polyhedron, which gives rise to a max-min fair allocation completely analogous to the conventional one.
G. Rétvári, J. J. Bíró, and T. Cinkler. Fairness in capacitated networks: a polyhedral approach. In IEEE INFOCOM 2007, Anchorage, Alaska, USA, May 2007. [ bib | DOI | slides [PDF] | paper [PDF] ]
Abstract - The problem of fair and feasible allocation of user throughputs in capacitated networks is investigated. The main contribution of the paper is a novel geometric approach, which facilitates to generalize several throughput allocation strategies, most importantly max-min fairness, from the traditional "fixed-path" model to a more versatile, routing-independent model. We show that the set of throughput configurations realizable in a capacitated network makes up a polyhedron, which gives rise to a max-min fair allocation completely analogous to the conventional one. An algorithm to compute this polyhedron is also presented, whose viability is demonstrated by comprehensive evaluation studies.
G. Rétvári. The geometry of networking, part I. In Proceedings of High Speed Networking 2007 Spring Workshop, Balatonkenese, Hungary, May 2007. [ bib ]
G. Rétvári, J. J. Bíró, and T. Cinkler. Novel methods for traffic engineering in legacy IP networks. In Proc., World Telecommunications Congress (WTC), Budapest, Hungary, May 2006. [ bib | paper [PDF] ]
Abstract - A short introduction, a comprehensive survey of the current state-of-the-art and an overview of some recent progress in the field of OSPF Traffic Engineering (TE) is given. Particularly, we study a multi-stage approach, where the original problem is divided into three subsequent and independent phases. This approach promises with breaking down the intractability of OSPF TE and also to provide interesting further insights. Finally, a simple heuristic is proposed, whose viability is demonstrated by simulation studies.
G. Rétvári, J. J. Bíró, and T. Cinkler. On improving the accuracy of OSPF Traffic Engineering. In Lecture Notes in Computer Science: Proceedings of the Fifth International IFIP-TC6 Networking Conference, pages 51--62, Coimbra, Portugal, 2006. [ bib | DOI | paper [PDF] ]
The conventional forwarding rule used by IP networks is to always choose the path with the shortest length -- in terms of administrative link weights assigned to the links -- to forward traffic. Lately, it has been proposed to use shortest-path-first routing to implement Traffic Engineering in IP networks, promising with a big boost in the profitability of the legacy network infrastructure. The idea is to set the link weights so that the shortest paths, and the traffic thereof, follow the paths designated by the operator. Unfortunately, traditional methods to calculate the link weights usually produce a bunch of superfluous shortest paths, often leading to congestion along the unconsidered paths. In this paper, we introduce and develop novel methods to increase the accuracy of this process and, by means of extensive simulations, we show that our proposed solution produces remarkably high quality link weights.
J. Tapolcai, P. Fodor, G. Rétvári, M. Maliosz, and T. Cinkler. Class-based minimum interference routing for traffic engineering in optical networks. In Proc., 1st EuroNGI Conference on Next Generation Internet Networks Traffic Engineering, Rome, Italy, April 2005. [ bib ]
G. Rétvári, J. J. Bíró, T. Cinkler, and T. Henk. A precomputation scheme for minimum interference routing: the Least-Critical-Path-First algorithm. In IEEE INFOCOM 2005, Miami, Florida, USA, March 2005. [ bib | DOI | paper [PDF] ]
This paper focuses on the selection of bandwidth-guaranteed channels for communication sessions that require it. The basic idea comes from Minimum Interference Routing: select a feasible path that puts the least possible restriction on the available transmission capacity of other communicating parties. This is achieved by circumventing some critical bottleneck links. The main contribution of the paper is a novel characterization of link criticality, the criticality threshold, which can be readily precomputed for routing dozens of subsequent calls. Based on this finding we define a generic precomputation framework for minimum interference routing, the Least-Critical-Path-First rout- ing algorithm. We show by means of extensive simulations that efficient route precomputation is possible even in the case, when accurate resource availability information is not immediately available.
G. Rétvári and T. Cinkler. Practical OSPF traffic engineering. IEEE Commununications Letters, 8:689--691, November 2004. [ bib | DOI | paper [PDF] ]
Open Shortest Path First (OSPF) traffic engineering (TE) is intended to bring long-awaited traffic management capabilities into IP networks, which still rely on today's prevailing routing protocols: OSPF or IS-IS. In OSPF, traffic is forwarded along, and split equally between, equal cost shortest paths. In this letter, we formulate the basic requirements placed on a practical TE architecture built on top of OSPF and present a theoretical framework meeting these requirements of practicality. The main contribution of our work comes from the recognition that coupled with an instance of the maximum throughput problem there exists a related inverse shortest-path problem yielding optimal OSPF link weights.
G. Rétvári, J. J. Bíró, and T. Cinkler. A novel Lagrangian-relaxation to the minimum cost multicommodity flow problem and its application to OSPF traffic engineering. In Proceedings of the The Ninth IEEE Symposium on Computers and Communications (ISCC'2004), volume 2, pages 957--962, Alexandria, Egypt, June 2004. [ bib | DOI | paper [PDF] ]
The Minimum Cost Multicommodity Flow problem plays a central role in today's operations research theory with applications ranging from transportation and logistics to telecommunications network routing. In this paper, we introduce a novel Lagrangian-relaxation technique, which, given an initial feasible solution, can solve the minimum cost multicommodity flow problem as a sequence of single-commodity flow problems. Our methodology is best suited for OSPF traffic engineering, because it can rapidly improve a given path set towards approximate optimality while simultaneously provides the link weights, which implement the paths as shortest paths.
G. Rétvári, J. J. Bíró, and T. Cinkler. Minimum interference routing: The precomputation perspective. In Proceedings of High Speed Networking 2004 Spring Workshop, pages 106--109, Budapest, Hungary, May 2004. [ bib ]
This paper focuses on the selection of bandwidth-guaranteed channels for communication sessions that require it. The basic idea comes from Minimum Interference Routing: select a feasible path that puts the least possible restriction on the transmission capacity offered by the network for other communicating parties. This is achieved by circumventing certain critical bottleneck links. The main contribution of the paper is a method to assess the degree of link criticality facilitating efficient route precomputation even in the case, when up to date resource availability information is not immediately available.
G. Rétvári, R. Szabó, and J. J. Bíró. On the representability of arbitrary path sets as shortest paths: Theory, algorithms, and complexity. In Lecture Notes in Computer Science: Proceedings of the Third International IFIP-TC6 Networking Conference, pages 1180--1191, Athens, Greece, May 2004. [ bib | DOI | paper [PDF] ]
The question, whether an optional set of routes can be represented as shortest paths, and if yes, then how, has been a rather scarcely investigated problem up until now. In turn, an algorithm that, given an arbitrary set of trafic engineered paths, can efficiently compute OSPF link weights as to map the given paths to shortest paths may be of huge importance in today's IP networks, which still rely on legacy shortest-path-first routing protocols. This article establishes the fundamental theory and algorithms of shortest path representability, and concludes that in general it is much more dificult task to compute shortest path representable paths than to actually calculate link weights for such paths.
J. Szigeti, J. Tapolcai, G. Rétvári, L. Láposi, and T. Cinkler. Útvonalkijelölés és forgalomelvezetés több tartományú kapcsolt optikai hálózatokban (hungarian). Híradástechnika, 59:42--49, February 2004. [ bib ]
G. Rétvári. Minimum interference routing: The precomputation perspective. In Proc., 6th IFIP/IEEE International Conference on Management of Multimedia Networks and Services (MMNS), Lecture Notes in Computer Science, pages 246--258, Belfast, UK, September 2003. [ bib | DOI | paper [PDF] ]
This paper focuses on the selection of bandwidth-guaranteed channels for communication sessions that require it. The basic idea comes from Minimum Interference Routing: select a feasible path that puts the least possible restriction on the transmission capacity offered by the network for other communicating parties. This is achieved by circumventing certain critical bottleneck links. The main contribution of the paper is a method to assess the degree of link criticality facilitating efficient route precomputation even in the case, when up to date resource availability information is not immediately available.
T. Szénási and G. Rétvári. Design and implementation of a traffic management functionality for RSVP. Híradástechnika (Communications), 57:21--27, December 2002. [ bib ]
J. Levendovszky, R. Szabó, G. Rétvári, Á. Marquetant, and Cs. Végső. Novel approach to traffic engineering in packet switched networks -- an analytic approach. In Proceedings of High Speed Networking 2002 Spring Workshop, pages 27--28, Budapest, Hungary, May 2002. [ bib ]
J. Levendovszky, G. Rétvári, and Cs. Végső. Statisztikus egyenlőtlenségek elméletén alapuló QoS útvonalkeresés hiányos linkinformáció esetén (hungarian). Híradástechnika, 56:3--13, November 2001. [ bib | paper [PDF] ]
J. Levendovszky, A. Fancsali, G. Rétvári, and Cs. Végső. QoS routing with incomplete information by analog computing algorithms. In Proceedings of 2nd International Workshop on Quality of future Internet Services, volume 56, pages 127--137, Coimbra, Portugal, September 2001. [ bib | DOI | paper [PDF] ]
The paper proposes novel algorithms for Quality of Service (QoS) routing in IP networks. The new algorithms can handle incomplete information, when link measures (e.g. link delays, bandwidths... etc.) are assumed to be random variables. Incomplete information can arise due to aggregated information in PNNI and OSPF routing protocols, which make link measures characterized by their corresponding p.d.f. It will be demonstrated that the task of QoS routing can be viewed as quadratic optimization. Therefore, neural based optimization algorithms implemented on an analog computer (CNN) can provide fast routing algorithms even in the case of incomplete information. As a result, real-time routing can be carried out to meet end-to-end QoS (such as end-to-end delay) requirements.
J. Levendovszky, T. Dávid, A. Fancsali, G. Rétvári, and Cs. Végső. QoS routing in packet switched networks -- novel algorithms for routing with incomplete information. In Proceedings of 9th IFIP Conference on Performance Modelling and Evaluation of ATM & IP Networks, pages 249--260, Budapest, Hungary, June 2001. [ bib | paper [PDF] ]
This paper investigates QoS routing in IP networks. The major concern is to select paths to fulfill end-to-end delay and minimum bandwidth requirements. Novel algorithms are developed to tackle routing with incomplete information, when link measures are subject to random fluctuations described by some given p.d.f.-s. The new algorithms are based on either assuming Gaussian link delay distribution or using large deviation theory to find the most likely path. The proposed methods are capable of QoS routing in polynomial time.
J. Levendovszky, A. Fancsali, Cs. Végső, and G. Rétvári. Quadratic optimization algorithms for QoS routing with incomplete information. In Proceedings of High Speed Networking 2001 Spring Workshop, pages 113--119, Balatonfüred, Hungary, May 2001. [ bib ]
G. Rétvári, R. Szabó, and Á. Marquetant. A novel approach to traffic engineering - core state limited load sharing. In Proceedings of PCH 2001 - 2001 Polish-Czech-Hungarian Workshop on Circuit Theory, Signal Processing, and Telecommunication Networks, pages 114--122, Budapest, Hungary, 2001. [ bib ]
G. Rétvári. Issues on QoS based routing in the Integrated Services Internet. In Proceedings of EUNICE '00, pages 69--76, Enschede, Netherlands, September 2000. [ bib | paper [PDF] ]
Given today's need for transmitting multimedia data over the Internet, large efforts have been made to specify and implement various service classes (Integrated Services: IntServ) over the well-known Internet Protocol (IP) infrastructure. Distinguishing service classes introduces the necessity of providing privileged treatment (QoS: Quality of Service) to a subset of data packets. Network resources dedicated to particular IP flows must be allocated at the initial phase of a QoS communication at each network node along the forwarding path. Calculation of this forwarding path is the responsibility of a separate routing module. While current routing protocols are not capable of considering QoS requirements when selecting paths, QoS enabled routing protocols increase the likelihood of accommodating a particular IP flow in the network according to its resource demands. Although the components of an IntServ platform are given, attempting to establish a functional testbed fails due to numerous design and implementation reasons. A brief investigation of the issues affecting the co-existence of resource reservation and QoS routing is provided in this paper. As currently IntServ can not take advantage of QoS routing, it is restricted to utilize traditional best-effort routing functionality. Several solutions are covered in this paper to avoid this limitation. A series of fundamental measurements are presented as well to demonstrate the efficiency of the QoS-routing enabled IntServ platform.
G. Rétvári and R. Szabó. QoS-based routing and IP multicasting: a framework. In Proceedings of EUNICE '99, pages 51--56, Barcelona, Spain, September 1999. [ bib | paper [PDF] ]
K. Kiss and G. Rétvári. Verification of a new scalable IP/ATM multicast routing protocol. In Proceedings of EUNICE '99, pages 89--94, Barcelona, Spain, September 1999. [ bib | paper [PDF] ]
This paper summarizes the work for defining and starting to verify a new protocol. The goal was to create a multicast routing protocol, which works in an IP over ATM network and, unlike the existing ones, is truly scalable. After studying the literature, we realized that no existing protocol is fully suitable for these requirements, so modifying an existing one we created a new routing protocol, and started to verify it using a formal description tool. In the first chapter we discuss the necessity of developing such a protocol. Next we provide the goals for the new protocol and the results of the studies of the existing proposals moreover some words are told about the essentials of our new protocol. In the third chapter we summarize the pros and the contras of the most scalable proposal: SEAM. In the fourth part of this documentation we show, how to manage the multicast tree in order to reach the best efficiency of network resource utilization. In the fifth chapter we provide a brief summary of the formal description of the new protocol. Finally in the sixth chapter we summarize the results of our verification studies.
K. Kiss and G. Rétvári. Multicast útvonalválasztás ATM feletti IP hálózatokban (hungarian). Magyar Távközlés, May 1999. [ bib ]
K. Kiss and G. Rétvári. SEAM and MNS: a new scalable multicast routing protocol in IP over ATM networks. In Proceedings of Vehicular Technology Conference, 1999. VTC 1999 - Fall. IEEE VTS 50th, volume 2, pages 1268--1272, 1999. [ bib ]
This file was generated by bibtex2html 1.99.
last modified: Tue Jan 2 02:49:44 PM CET 2024