text:
research unit 1
- Report Number
- Alphabetic
- Type
- Recent
- Incomplete
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.
Titles (60) Keywords (26) Abstracts (109)
[RACTI-RU1-2017-43] Giannakopoulou, Kalliopi, Kontogiannis, Spyros, Papastavrou, Georgia and Zaroliagis, Christos, A Cloud-based Time-Dependent Routing Service, in: Algorithmic Aspects of Cloud Computing - ALGOCLOUD 2016, volume 10230, pages 41-64, 2017.
[RACTI-RU1-2006-86] Manousakis, Kostas, Sourlas, Vasileios, Stampoulidis, L., Vlachos, Kyriakos and Varvarigos, Emmanouel, A link capacity monitoring mechanism, suitable for traffic engineering and QoS routing by enhancing SNMP to record bandwidth reservations, in: Journal of Network and Systems Management, volume 14, number 4, pages 583-597, 2006.
[RACTI-RU1-2008-6] Bamis, Athanasios, Boukerche, Azzedine, Chatzigiannakis, Ioannis and Nikoletseas, Sotiris, A Mobility Aware Protocol Synthesis for Efficient Routing in Ad-Hoc Mobile Networks, in: Computer Networks, volume 52, number 1, pages 130-154, 2008. [DOI]
[RACTI-RU1-2006-29] Bamis, Athanasios, Boukerche, Azzedine, Chatzigiannakis, Ioannis and Nikoletseas, Sotiris, A Mobility Sensitive Approach for Efficient Routing in Ad Hoc Mobile Networks, in: 9th ACM/IEEE Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM 2006), pages 357-364, Torremolinos, Malaga, Spain, 2006.
[RACTI-RU1-2007-20] Chatzigiannakis, Ioannis, Mylonas, Georgios and Nikoletseas, Sotiris, A Model for Obstacles to be used in Simulations of Wireless Sensor Networks and its Application in studying Routing Protocol Performance, in: SCS Simulation: Transactions of the Society for Modeling and Simulation International, volume 83, number 8, pages 587-608, 2007. [DOI]
[RACTI-RU1-2003-52] Chi-Hsiang, Yeh, Varvarigos, Emmanouel and Eshoul, Abdelhamid, A priority-based balanced routing scheme for random broadcasting and routing in tori, in: 32nd International Conference on Parallel Processing (ICPP 2003), pages 519-526, Queen's Univ., Kingston, Ont., Kaohsiung, Taiwan, 2003. [DOI]
[RACTI-RU1-2008-27] Bairaktaris, Kostantinos, Chatzigiannakis, Ioannis, Liagkou, Vasiliki and Spirakis, Paul, Adaptive Probabilistic Secure Routing in Mobile Wireless Sensor Networks, in: 16th International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2008), pages 208-212, IEEE, IEEE, Split - Dubrovnik, Croatia, 2008. [DOI]
[RACTI-RU1-2003-63] Varvarigos, Emmanouel, Varvarigou, T. and Verentziotis, E., Adaptive Routing and Wavelength Assignment in All-Optical Networks: the role of Wavelength Conversion and Virtual Circuit Deflection, CRC Press, pages 221-246, 2003.
[RACTI-RU1-2001-4] Chatzigiannakis, Ioannis, Nikoletseas, Sotiris and Spirakis, Paul, An Efficient Routing Protocol for Hierarchical Ad-hoc Mobile Networks, in: 1st IEEE/ACM International Workshop on Parallel and Distributed Computing Issues in Wireless networks and Mobile Computing, pages 185, IEEE/ACM, IEEE/ACM, San Francisco, USA, 2001.
[RACTI-RU1-2010-33] Athanassopoulos, Stavros, Kaklamanis, Christos, Laftsidis, Ilias and Papaioannou, Evi, An Experimental Study of Greedy Routing Algorithms, in: The 2010 International Confernce onHigh Performance Computing & Simulation (HPCS), France, 2010.
[RACTI-RU1-2000-3] Chatzigiannakis, Ioannis, Nikoletseas, Sotiris and Spirakis, Paul, Analysis and Experimental Evaluation of an Innovative and Efficient Routing Protocol for Ad-hoc Mobile Networks, in: 4th Workshop on Algorithmic Engineering (WAE 2000), pages 99-110, Springer-Verlag, Saarbrcken, Germany, 2000.
[RACTI-RU1-2010-47] Efstathiou, Dionysios, Koutsopoulos, A and Nikoletseas, Sotiris, Analysis and Simulation for Parameterizing the Energy-Latency Trade-off for Routing in Sensor Networks, in: 12th ACM MSWiM 2010 Technical Program, 2010.
[RACTI-RU1-2005-25] Vyrsokinos, K, Kehayas, E., Stampoulidis, L., Avramopoulos, Hercules, Christodoulopoulos, Konstantinos, Vlachos, Kyriakos and Varvarigos, Emmanouel, ARTEMIS: A New Architecture for All-Optical Asychronous Self -Routing Network with Efficient Contention Protection and QoS Differentiation, IEEE proceedings of 31st European Conference on Optical Communications (ECOC) SECC, 2005.
[RACTI-RU1-2005-29] Stampoulidis, L., Kehayas, E., Vyrsokinos, K, Christodoulopoulos, Konstantinos, Tsiokos, D, Bakopoulos, , Kanellos, T, Vlachos, Kyriakos, Varvarigos, Emmanouel and Avramopoulos, Hercules, ARTEMIS:A 40 Gb/s All-Optical Self-Routing Node and Network Architecture employing Asynchronous Bit and Packet-Level Optical Signal Processing, in: IEEE Global Telecommunications Conference (GLOBECOM 2005), pages 2035-2040, St Louis USA, 2005.
[RACTI-RU1-2005-43] Kontogiannis, Spyros and Spirakis, Paul, Atomic Selfish Routing in Networks, in: 1st Workshop on Internet and Network Economics (WINE 2005), pages 989-1002, 2005.
[RACTI-RU1-2016-36] Spirakis, Paul, Best Response Algorithms for Selfish Routing, in: Encyclopedia of Algorithms, pages 181-183, 2016. [DOI]
[RACTI-RU1-2008-17] Christodoulopoulos, Konstantinos, Manousakis, Kostas and Varvarigos, Emmanouel, Comparison of Routing and Wavelength Assignment Algorithms in WDM Networks, in: 51st IEEE Global Telecommunications Conference, 2008.
[RACTI-RU1-2007-102] Vlachos, Kyriakos, Breusegem, E., Christodoulopoulos, Konstantinos, Colle, Didier, Ramantas, Kostas and Demeester, Piet, Constrained and Unconstrained Overspill Routing in Optical Networks: A Detailed Performance Evaluation, in: Springer: Journal on Photonic Network Communications, volume 13, number 3, pages 227-240, 2007.
[RACTI-RU1-2006-77] Busch, Costas, Magdon-Ismail, Malik, Mavronicolas, Marios and Spirakis, Paul, Direct Routing: Algorithms and Complexity, in: Algorithmica, volume 45, number 1, pages 45-68, 2006. [DOI]
[RACTI-RU1-2004-8] Busch, Costas, Magdon-Ismail, Malik, Mavronicolas, Marios and Spirakis, Paul, Direct Routing: Algorithms and Complexity, in: ESA 2004, pages 134-145, 2004.
[RACTI-RU1-2006-9] Bender, Matthias, Michel, Sebastian, Ntarmos, Nikos, Triantafillou, Peter, Weikum, Gerhard and Zimmer, Christian, Discovering and Exploiting Keyword and Attribute-Value Co-occurrences to Improve P2P Routing Indices, in: 15th ACM Conference on Information and Knowledge Management (CIKM 2006), 2006.
[RACTI-RU1-2017-40] Dibbelt, J., Gavalas, Damianos, Giannakopoulou, Kalliopi, Konstantopoulos, Charalampos, Kontogiannis, Spyros and Pantziou, Grammati, Eco-aware Vehicle Routing in Urban Environments, in: 22nd IEEE International Symposium on Computer and Communications (ISCC�2017), IEEE Computer Society, ISCC�2017, 2017.
[RACTI-RU1-2014-32] Gkortsilas, Dimitrios and Zaroliagis, Christos, Eco-friendly Vehicle Routing via Balanced and Compact Clustering, in: 3rd Workshop on Vehicle Routing and Logistics Optimization, VeRoLog 2014, 2014.
[RACTI-RU1-2005-26] Kokkinos, Panagiotis, Papageorgiou, Christos and Varvarigos, Emmanouel, Energy-Aware Routing in Wireless Ad-hoc Networks, in: 6th IEEE International Symposium on a Word of Wireless Mobile and Multimedia Networks, pages 306-311, 2005.
[RACTI-RU1-2017-47] Veneti, A., Konstantopoulos, Charalampos and Pantziou, Grammati, Evolutionary Computation for the Ship Routing Problem, in: Modelling, Computing and Data Handling Methodologies for Maritime Transportation, volume 4, pages 95-115, 2017.
[RACTI-RU1-2009-45] Nikoletseas, Sotiris, Powell, Olivier and Rolim, Jose, Geographic Routing of Sensor Data around Voids and Obstacles, chapter in the book "Intelligent Techniques for Warehousing and Mining Sensor Network Data", 2009.
[RACTI-RU1-2008-19] Papageorgiou, Christos, Kokkinos, Panagiotis and Varvarigos, Emmanouel, Implementing Distributed Multicost Routing in Mobile Ad Hoc Networks using DSR, in: 6th ACM International Workshop on Mobility Management and Wireless Access(MOBIWAC 2008), pages 35-42, Mobiwac 2008, 2008.
[RACTI-RU1-2006-17] Michel, Sebastian, Bender, Matthias, Triantafillou, Peter and Weikum, Gerhard, IQN Routing: Integrating Quality and Novelty in P2P Querying and Ranking, in: 10th International Conference on Extending Database Technology (EDBT 2006), pages 62-67, 2006.
[RACTI-RU1-2010-53] Karagiorgas, Nikos, Kokkinos, Panagiotis, Papageorgiou, Christos and Varvarigos, Emmanouel, Joint multi-cost routing and power control in wireless ad hoc networks, in: Wireless Networks, volume 16, number 8, 2010. [DOI]
[RACTI-RU1-2010-58] Manousakis, Kostas, Kokkinos, Panagiotis, Christodoulopoulos, Konstantinos and Varvarigos, Emmanouel, Joint Online Routing, Wavelength Assignment and Regenerator Allocation in Translucent Optical Networks, in: Lightwave Technology, volume 28, number 8, pages 1152-1163, 2010.
[RACTI-RU1-2017-48] Veneti, A., Makrygiorgos, A., Konstantopoulos, Charalampos, Pantziou, Grammati and Vetsikas, I., Minimizing the fuel consumption and the risk in maritime transportation: A bi-objective weather routing approach, in: Computers and Operations Research Journal, Elsevier, volume 88, pages 220-236, 2017.
[RACTI-RU1-2008-67] Stevens, T, De Leenheer, M., Develder, C., Dhoedt, B., Christodoulopoulos, Konstantinos, Kokkinos, Panagiotis and Varvarigos, Emmanouel, Multi-Cost Job Routing and Scheduling in Grid Networks, in: Elsevier: Journal of Future Generation Computer Systems, 2008.
[RACTI-RU1-2011-82] Kokkinos, Panagiotis, Papageorgiou, Christos and Varvarigos, Emmanouel, Multi-cost Routing for Energy and Capacity Constrained Wireless Mesh Networks, in: Wireless Communications and Mobile Computing, 2011.
[RACTI-RU1-2007-99] Karagiorgas, Nikos, Kokkinos, Panagiotis, Papageorgiou, Christos and Varvarigos, Emmanouel, Multicost routing in Wireless Ad-hoc Networks with Variable Transmission Power, in: IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2007), pages 1-5, 2007.
[RACTI-RU1-2006-54] Papageorgiou, Christos, Kokkinos, Panagiotis and Varvarigos, Emmanouel, Multicost Routing over an Infinite Time Horizon in Energy and Capacity Constrained Wireless Ad-hoc Networks, in: 12th International Euro-Par Conference (Euro-Par 2006), pages 931-940, Springer-Verlag, 2006.
[RACTI-RU1-2007-8] Moraru, Luminita, Leone, Pierre, Nikoletseas, Sotiris and Rolim, Jose, Near optimal geographic routing with obstacle avoidance in wireless sensor networks by fast-converging trust-based algorithms, in: 3rd ACM International Workshop on QoS and Security for Wireless and Mobile Networks (Q2SWINET 2007), pages 31-38, ACM Press, 2007.
[RACTI-RU1-2010-57] Christodoulopoulos, Konstantinos, Manousakis, Kostas and Varvarigos, Emmanouel, Offline Routing and Wavelength Assignment in Transparent WDM Networks, in: IEEE/ACM Transactions on Networking, volume 18, number 5, pages 1557-1570, 2010.
[RACTI-RU1-2014-24] Fotakis, Dimitris, Kaporis, Alexis, Lianeas, Thanasis and Spirakis, Paul, On the Hardness of Network Design for Bottleneck Routing Games, in: Theoretical Computer Science (TCS), volume 521, number 13, pages 107-122, 2014.
[RACTI-RU1-2011-85] Christodoulopoulos, Konstantinos and Varvarigos, Emmanouel, Online Impairment Aware Routing and Wavelength Assignment in WDM Optical Networks, in: Online Impairment Aware Routing and Wavelength Assignment in WDM Optical Networks, volume 6, ISSN 978-1-61470-455-3, 2011.
[RACTI-RU1-2010-9] Moraru, Luminita, Leone, Pierre, Nikoletseas, Sotiris and Rolim, Jose, Path quality detection algorithms for near optimal geographic routing in sensor networks with obstacles, in: Wireless Communications and Mobile Computing, pages 647-661, 2010.
[RACTI-RU1-2004-31] Tomkos, Ioannis, Vogiatzis, D, Mas, C, Zacharopoulos, I and Tzanakaki, A, Performance Engineering of Metropolitan Area Optical Networks through Impairment Constraint Routing, in: IEEE Communications Magazine, pages 40-47, 2004.
[RACTI-RU1-2004-32] Tomkos, Ioannis, Vogiatzis, D, Mas, C, Zacharopoulos, I, Tzanakaki, A and Varvarigos, Emmanouel, Performance Engineering of Metropolitan Area Optical Networks through Impairment Constraint Routing, in: IEEE Communications Magazine, volume 42, number 8, pages 40-47, 2004.
[RACTI-RU1-2006-62] Christodoulopoulos, Konstantinos, Breusegem, E., Vlachos, Kyriakos, Pickavet, Mario, Varvarigos, Emmanouel and Colle, Didier, Performance Evaluation of Overspill Routing in Optical Networks, in: IEEE International Conference on Communications (ICC 2006), pages 2583-2543, Instanbul, Turkey, 2006.
[RACTI-RU1-2009-48] Nikoletseas, Sotiris and Spirakis, Paul, Probabilistic Distributed Algorithms for Energy Efficient Routing and Tracking in Wireless Sensor Networks, in: Algorithms Journal, volume 2, number 1, pages 121-157, 2009.
[RACTI-RU1-2008-21] Varvarigos, Emmanouel, Sourlas, Vasileios and Christodoulopoulos, Konstantinos, Routing and Scheduling Connections in Networks that Support Advance Reservations, in: Elsevier: Journal of Computer Networks, volume 52, pages 2988-3006, 2008.
[RACTI-RU1-2008-54] Christodoulopoulos, Konstantinos and Varvarigos, Emmanouel, Routing and Scheduling in Grids, in: 10th Anniversary International Conference on Transparent Optical Networks, pages 170-174, ICTON 3, Athens, Greece, 2008. [DOI]
[RACTI-RU1-2008-84] Varvarigos, Emmanouel, Sourlas, Vasileios and Christodoulopoulos, Konstantinos, Routing and Scheduling Sessions in Networks that Support Advance Reservations, 2008.
[RACTI-RU1-2008-16] Varvarigos, Emmanouel, Sourlas, Vasileios and Christodoulopoulos, Konstantinos, Routing and Scheduling Sessions in Networks that Support Advance Reservations, in: 5th IEEE BROADNETS, pages 2988-3006, 2008.
[RACTI-RU1-2010-62] Christodoulopoulos, Konstantinos, Tomkos, Ioannis and Varvarigos, Emmanouel, Routing and Spectrum Allocation Algorithms in OFDM-enabled Optical Networks, in: Globecom 2010, 2010.
[RACTI-RU1-2016-57] Massri, Khalil, Vitaletti, Andrea, Vernata, Alessandro and Chatzigiannakis, Ioannis, Routing Protocols for Delay Tolerant Networks: A Reference Architecture and a Thorough Quantitative Evaluation, in: Journal of Sensor and Actuator Networks — Open Access Journal, volume 5, number 2, pages 6, 2016. [DOI]
[RACTI-RU1-2006-25] Chatzigiannakis, Ioannis, Kokkinos, Panagiotis and Zaroliagis, Christos, Routing Protocols for Efficient Communication in Wireless Ad-hoc Networks, in: 3rd ACM Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks, pages 90-97, ACM, PE-WASUN 2006, Torremolinos, Malaga, Spain, 2006.
[RACTI-RU1-2005-81] Kontogiannis, Spyros and Spirakis, Paul, Selfish Routing and Congestion: A Survey, in: 2nd European Conference on Complex Systems (ECCS 2005), 2005.
[RACTI-RU1-2004-70] Nikoletseas, Sotiris and Spirakis, Paul, self-organization of dynamic network entities for low connection routing via random walks, in: DELIS Workshop on Algorithmic Problems in ad-hoc networks, Wroclaw, Poland, 2004.
[RACTI-RU1-2007-9] Powell, Olivier and Nikoletseas, Sotiris, Simple and Efficient Geographic Routing around Obstacles for Wireless Sensor Networks, in: 6th International Workshop on Experimental Algorithms (WEA 2007), pages 161-174, Springer Verlag, LNCS, 2007. [DOI]
[RACTI-RU1-2005-83] Kontogiannis, Spyros, Fotakis, Dimitris and Spirakis, Paul, Symmetry in Selfish Routing, in: 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), Springer-Verlag, 2005.
[RACTI-RU1-2004-25] Chatzigiannakis, Ioannis, Kokkinos, Panagiotis and Zaroliagis, Christos, Synthesizing Routing Protocols for Ad-hoc Mobile Networks, in: 12th Annual IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pages 634-637, IEEE/ACM, IEEE/ACM, MASCOTS 2004, Netherlands, 2004.
[RACTI-RU1-2007-107] Mavronicolas, Marios and Spirakis, Paul, The Price of Selfish Routing, in: Algorithmica, volume 48, number 1, pages 91-126, ISSN 0178-4617 (Print) 1432-0541 (Onl, 2007. [DOI]
[RACTI-RU1-2001-15] Mavronicolas, Marios and Spirakis, Paul, The price of selfish routing, in: Symposium on Theory of Computing (2001), pages 510-519, 2001.
[RACTI-RU1-2002-8] Fotakis, Dimitris, Kontogiannis, Spyros, Koutsoupias, Elias, Mavronicolas, Marios and Spirakis, Paul, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, in: International Colloquium on Automata, Languages and Programming, pages 123-134, 2002.
[RACTI-RU1-2005-9] Weikum, Gerhard, Hales, David, Schindelhauer, Christian and Triantafillou, Peter, Towards Self-Organizing Query Routing and Processing for Peer-to-Peer Web Search, in: European Conference on Complex Systems (ECCS 2005), 2005.
Add all checked publications to topic... ----Top ABC4TRUST AEOLUS SP1 - Paradigms and principles WP1.1 - Structural Properties WP1.2 - Coping with Incomplete Knowledge WP1.3 - Coping with Selfishness WP1.4 - Stability and Fault-Tolerance WP1.5 - Generic Algorithms SP2 - Resource management WP2.1 - Resource Discovery WP2.2 - Sharing Critical Resources WP2.3 - Mechanism Design SP3 - Sharing information and computation WP3.1 - Distributed Data Management WP3.2 - Load Management WP3.3 - Scheduling WP3.4 - Workflow and Services SP5 - Extending global computing to wireless users WP5.1 - Resource Management and Quality-of-Service (QoS) WP5.2 - Dynamical Aspects of Network Design and Topology Control WP5.3 - Mobility and Fault Tolerance SP6 - Design and implementation of components and applications for programmable overlay computers WP6.1 - Specification and design of the platform WP6.2 - Implementation of platform components WP6.3 - Integration and testing of the platform ALCOM II ALCOM-FT ALCOM-IT AMORE ARACNE ARRIVAL AUDIS DELIS FLAGS FOCUS FRONTS HOBNET PENED/AEGT PENED/ALGODES PENED/ALKAD PENED/P2P PENED/QoS RIMACO SmartSantander SpitFIRE VITRO WISEBED
Export to... BibTeX RIS More...
Keywords: Sensor networks, obstacles, modeling, environment, deployment, routing, performance,
[RACTI-RU1-2009-51] Angelopoulos, Constantinos Marios and Nikoletseas, Sotiris, Accelerated Sensory Data Collection by Greedy or Aggregate Mobility-based Topology Ranks, in: 6th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN 2009), Canary Islands, Spain, 2009.
Keywords: Wireless Sensor Networks, Routing, Aggregation, Performance Evaluation
[RACTI-RU1-2011-93] Adapting the Transmission Reach in Mixed Line Rates WDM Transport Networks, in: 15th Conference on Optical Network Design and Modeling, ONDM 2011, 2011.
Keywords: Wavelenth Division Multiplexing (WDM), Mixed line rates (MLR), Routing and Wavelenth Assignment (RWA), planning (offline) phase, transmission reach.
[RACTI-RU1-2011-57] Angelopoulos, Constantinos Marios and Nikoletseas, Sotiris, Aggregated mobility-based topology inference for fast sensor data collection, in: Journal Computer Communications, volume 34, number 13, pages 1570-1579, 2011. [DOI]
[RACTI-RU1-2011-88] Varvarigos, Emmanouel and Christodoulopoulos, Konstantinos, Algorithmic aspects of optical network design, in: 15th Conference on Optical Network Design and Modeling, ONDM, 2011.
Keywords: Network optimization, Linear Programming (LP), Integer Linear Programming (ILP), LP-relaxation, Routing and Wavelenth Assignment
Keywords: greedy routing, long range contacts, peerto- peer systems, experimental evaluation.
Keywords: Wireless Sensor Networks, Algorithms, Data Propagation, Energy Efficiency, Routing, Performance Evaluation
[RACTI-RU1-2008-52] Christodoulopoulos, Konstantinos, Manousakis, Kostas and Varvarigos, Emmanouel, Avoiding adjacent channel interference in static RWA, pages 552-556, 2008.
Keywords: Routing and Wavelength Assignment, offline traffic, LP relaxation, adjacent channel interference
Keywords: Hybrid optical switching , Optical networks , Overspill routing , Photonic switching systems
[RACTI-RU1-2004-18] Chatzigiannakis, Ioannis and Nikoletseas, Sotiris, Design and Analysis of an Efficient Communication Strategy for Hierarchical and Highly Changing Ad-hoc Mobile Networks, in: Journal of Mobile Networks and Applications, volume 9, number 4, pages 319-332, 2004. [DOI]
Keywords: ad-hoc mobile networks, routing, average case analysis, random walks, experimental evaluation
Keywords: Vehicle Routing Problem with Time Windows (VRPTW), geographic partition, compact and balanced clustering
[RACTI-RU1-2011-8] Kokkinos, Panagiotis, Christodoulopoulos, Konstantinos and Varvarigos, Emmanouel, Efficient data consolidation in grid networks and performance analysis, in: Future Generation Computer Systems, volume 27, number 2, pages 182-194, 2011. [DOI]
Keywords: Grids, Task scheduling, Data migration, Routing
Keywords: sensor networks, routing, obstacle avoidance, distributed algorithms, data management
Keywords: wireless mesh networks, multi-cost routing, energy and capacity constraints
[RACTI-RU1-2009-50] Koutsopoulos, A, Nikoletseas, Sotiris and Rolim, Jose, Near optimal Data Propagation by Efficiently Advertising Obstacle Boundaries, in: 6th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN 2009), Canary Islands, Spain, 2009.
Keywords: sensor networks, obstacle avoidance, routing, performance evaluation
Keywords: geographic routing, QoS routing, obstacle avoidance, void-handling, communication void, geographic ad-hoc routing, optimal path, sensor networks
[RACTI-RU1-2010-16] Nikoletseas, Sotiris, On the energy balance problem in distributed sensor networks, in: Computer Science Review, volume 4, number 2, pages 65-79, 2010.
Keywords: Distributed computing, Sensor networks, Energy efficiency, Routing, Probabilistic algorithms
[RACTI-RU1-2009-108] Christodoulou, George, Koutsoupias, Elias and Spirakis, Paul, On the Performance of Approximate Equilibria in Congestion Games, in: 17th Annual European Symposium Algorithms, Denmark, 2009.
Keywords: Price of anarchy Price of stability Congestion games Algorithmic Game Theory Approximate equilibria Selfish routing
[RACTI-RU1-2007-82] Konstantopoulos, Charalampos and Kaklamanis, Christos, Optimal Hypercube Simulation on the Partitioned Optical Passive Stars Network, in: Journal of Supercomputing, volume 42, number 2, pages 165-180, ISSN 0920-8542 (Print) 1573-0484 (Onl, 2007. [DOI]
Keywords: Hypercube , Optical networks , Partitioned Optical Passive Stars (POPS) network , Routing , Network mapping
Keywords: geographic routing,QoS routing, obstacle avoidance, communication void ,optimal path,sensor networks
Keywords: sensor networks, energy efficiency, routing, tracking, distributed algorithms, probabilistic methods
[RACTI-RU1-2011-61] Christodoulopoulos, Konstantinos, Manousakis, Kostas and Varvarigos, Emmanouel, Reach Adapting Algorithms for Mixed Line Rate WDM Transport Networks, in: JTL, 2011.
Keywords: Wavelenth Division Multiplexing (WDM), Mixed line rate (MLR) optical network, Routing and Wavelenth Assignment (RWA), planning (offline) phase, transmission reach, cross-rate interference.
Keywords: sensor networks, obctacle avoidance, geographic routing
[RACTI-RU1-2005-62] Mavronicolas, Marios, Monien, Burkhart, Gairing, Martin, Luecking, T. and Spirakis, Paul, Structure and complexity of extreme Nash equilibria, in: Theoretical Computer Science (TCS), volume 343, number 1-2, pages 133-157, 2005. [DOI]
Keywords: Selfish routing; Extreme Nash equilibria
[RACTI-RU1-2005-50] Gairing, Martin, Lucking, Thomas, Mavronicolas, Marios, Monien, Burkhart and Spirakis, Paul, Structure and complexity of extreme Nash equilibria, in: Theoretical Computer Science (TCS), volume 343, number 1-2, pages 133-157, 2005.
Keywords: Selfish routing; Extreme Nash equilibria References
Keywords: Nash equilibria, Coordination ratio, Selfish routing, Fully mixed Nash equilium.
[RACTI-RU1-2009-126] Christodoulopoulos, Konstantinos, Sourlas, Vasileios, Mpakolas, I and Varvarigos, Emmanouel, A Comparison of Centralized and Distributed Meta-Scheduling Architectures for Computation and Communication Tasks in Grid Networks, in: Computer Communications, volume 32, number 7-10, pages 1172-1184, 2009.
The management of Grid resources requires scheduling of both computation and communication tasks at various levels. In this study, we consider the two constituent sub-problems of Grid scheduling, namely: (i) the scheduling of computation tasks to processing resources and (ii) the routing and scheduling of the data movement in a Grid network. Regarding computation tasks, we examine two typical online task scheduling algorithms that employ advance reservations and perform full network simulation experiments to measure their performance when implemented in a centralized or distributed manner. Similarly, for communication tasks, we compare two routing and data scheduling algorithms that are implemented in a centralized or a distributed manner. We examine the effect network propagation delay has on the performance of these algorithms. Our simulation results indicate that a distributed architecture with an exhaustive resource utilization update strategy yields better average end-to-end delay performance than a centralized architecture.
[RACTI-RU1-2009-62] Azodolmolky, Siamak, Klonidis, Dimitris, Tomkos, Ioannis, Ye, Yabin, Saradhi, Chava Vijaya, Salvadori, Eliot, Gunkel, Matthias, Manousakis, Kostas, Vlachos, Kyriakos, Varvarigos, Emmanouel, Nejabati, Reza, Simeonidou, Dimitra, Eiselt, Michael, Comellas, Jaume, Sole-Pareta, Josep, Simonneau, Christian, Bayart, Dominique, Staessens, Dimitri, Colle, Didier and Pickavet, Mario, A Dynamic Impairment-Aware Networking Solution for Transparent Mesh Optical Networks, in: IEEE Communications Magazine, volume 47, number 5, pages 38-47, 2009.
Core networks of the future will have a translucent and eventually transparent optical structure. Ultra-high-speed end-to-end connectiv- ity with high quality of service and high reliability will be realized through the exploitation of opti- mized protocols and lightpath routing algorithms. These algorithms will complement a flexible con- trol and management plane integrated in the proposed solution. Physical layer impairments and optical performance are monitored and incorporated in impairment-aware lightpath rout- ing algorithms. These algorithms will be integrat- ed into a novel dynamic network planning tool that will consider dynamic traffic characteristics, a reconfigurable optical layer, and varying physi- cal impairment and component characteristics. The network planning tool along with extended control planes will make it possible to realize the vision of optical transparency. This article pre- sents a novel framework that addresses dynamic cross-layer network planning and optimization while considering the development of a future transport network infrastructure.
[RACTI-RU1-2013-22] Angelopoulos, Constantinos Marios, Filios, Gabriel, Nikoletseas, Sotiris, Patroumpa, Dimitra, Raptis, Theofanis and Veroutis, Konstantinos, A holistic IPv6 test-bed for smart, green buildings, pages 6050-6054, ICC 2013, 2013.
This work addresses networked embedded systems enabling the seam- less interconnection of smart building automations to the Internet and their abstractions as web services. In our approach, such abstractions are used to primarily create a exible, holistic and scalable system and allow external end-users to compose and run their own smart/green building automation application services on top of this system. Towards this direction, in this paper we present a smart building test- bed consisting of several sensor motes and spanning across seven rooms. Our test-bed's design and implementation simultaneously addresses sev- eral corresponding system layers; from hardware interfaces, embedded IPv6 networking and energy balancing routing algorithms to a RESTful architecture and over the web development of sophisticated, smart, green scenarios. In fact, we showcase how IPv6 embedded networking combined with RESTful architectures make the creation of building automation ap- plications as easy as creating any other Internet Web Service.
In mobile ad-hoc networks (MANETs), the mobility of the nodes is a complicating factor that significantly affects the effectiveness and performance of the routing protocols. Our work builds upon recent results on the effect of node mobility on the performance of available routing strategies (i.e.~path based, using support) and proposes a protocol framework that exploits the usually different mobility rates of the nodes by adapting the routing strategy during execution. We introduce a metric for the relative mobility of the nodes, according to which the nodes are classified into mobility classes. These mobility classes determine, for any pair of an origin and destination, the routing technique that best corresponds to their mobility properties. Moreover, special care is taken for nodes remaining almost stationary or moving with high (relative) speeds. Our key design goal is to limit the necessary implementation changes required to incorporate existing routing protocols in to our framework. We provide extensive evaluation of the proposed framework, using a well-known simulator (NS2). Our first findings demonstrate that the proposed framework improves, in certain cases, the performance of the existing routing protocols.
In ad-hoc mobile networks (MANET), the mobility of the nodes is a complicating factor that significantly affects the effectiveness and performance of the routing protocols. Our work builds upon the recent results on the effect of node mobility on the performance of available routing strategies (i.e.~path based, using support) and proposes a protocol framework that exploits the usually different mobility rates of the nodes by adopting the routing strategy during execution. We introduce a metric for the relative mobility of the nodes, according to which the nodes are classified into mobility classes. These mobility classes determine, for any pair of origin and destination, the routing technique that best corresponds to their mobility properties. Moreover, special care is taken for nodes remaining almost stationary or moving with high (relative) speeds. Our key design goal is to limit the necessery implementation changes required to incorporate existing routing protocols in our framework. We provide extensive evaluation of the proposed framework, using a well-known simulator (NS2). Our first findings demonstrate that the proposed framework improves, in certain cases, the performance of the existing routing protocols.
We propose a simple obstacle model to be used while simulating wireless sensor networks. To the best of our knowledge, this is the first time such an integrated and systematic obstacle model for these networks has been proposed. We define several types of obstacles that can be found inside the deployment area of a wireless sensor network and provide a categorization of these obstacles based on their nature (physical and communication obstacles, i.e. obstacles that are formed out of node distribution patterns or have physical presence, respectively), their shape and their change of nature over time. We make an eXtension to a custom-made sensor network simulator (simDust) and conduct a number of simulations in order to study the effect of obstacles on the performance of some representative (in terms of their logic) data propagation protocols for wireless sensor networks. Our findings confirm that obstacle presence has a significant impact on protocol performance, and also that different obstacle shapes and sizes may affect each protocol in different ways. This provides an insight into how a routing protocol will perform in the presence of obstacles and highlights possible protocol shortcomings. Moreover, our results show that the effect of obstacles is not directly related to the density of a sensor network, and cannot be emulated only by changing the network density.
[RACTI-RU1-2009-119] Christodoulopoulos, Konstantinos, Manousakis, Kostas, Varvarigos, Emmanouel, Angelou, M. and Tomkos, Ioannis, A Multicost Approach to Online Impairment-Aware RWA, in: IEEE International Conference on Communications, Dresden, 2009.
We design and implement a multicost impairment- aware routing and wavelength assignment algorithm for online traffic. In transparent optical networks the quality of a transmission degrades due to physical layer impairments. To serve a connection, the proposed algorithm finds a path and a free wavelength (a lightpath) that has acceptable signal quality performance by estimating a quality of transmission measure, called the Q factor. We take into account channel utilization in the network, which changes as new connections are established or released, in order to calculate the noise variances that correspond to physical impairments on the links. These, along with the time invariant eye impairment penalties of all candidate network paths, form the inputs to the algorithm. The multicost algorithm finds a set of so called non-dominated Q paths from the given source to the given destination. Various objective functions are then evaluated in order to choose the optimal lightpath to serve the connection. The proposed algorithm combines the strength of multicost optimization with low execution time, making it appropriate for serving online connections.
[RACTI-RU1-2008-71] Vlachos, Kyriakos and Ramantas, Kostas, A non-competing hybrid optical burst switch architecture for QoS differentiation, in: Optical Switching and Networking, volume 5, number 4, pages 177-187, 2008. [DOI]
In this paper, we present a new hybrid optical burst switch architecture (HOBS) that takes advantage of the pre-transmission idle time during lightpath establishment. In dynamic circuit switching (wavelength routing) networks, capacity is immediately hardreserved upon the arrival of a setup message at a node, but it is used at least a round-trip time delay later. This waste of resources is significant in optical multi-gigabit networks and can be used to transmit traffic of a lower class of service in a non-competing way. The proposed hybrid OBS architecture, takes advantage of this idle time to transmit one-way optical bursts of a lower class of service, while high priority data explicitly requests and establishes end-to-end lightpaths. In the proposed scheme, the two control planes (two-way and one-way OBS reservation) are merged, in the sense that each SETUP message, used for the two-way lightpath establishment, is associated with one-way burst transmission and therefore it is modified to carry routing and overhead information for the one-way traffic as well. In this paper, we present the main architectural features of the proposed hybrid scheme and further we assess its performance by conducting simulation experiments on the NSF net backbone topology. The extensive network study revealed that the proposed hybrid architecture can achieve and sustain an adequate burst transmission rate with a finite worst case delay.
[RACTI-RU1-2014-35] Gavalas, Damianos, Kasapakis, Vlasios, Konstantopoulos, Charalampos, Pantziou, Grammati, Vathis, Nikolaos and Zaroliagis, Christos, A Personalized Multimodal Tourist Tour Planner, in: 13th International Conference on Mobile and Ubiquitous Multimedia, pages 73-80, MUM 2014 (ACM), 2014.
Tourists become increasingly dependent on mobile city guides to locate tourist services and retrieve information about nearby points of interest (POIs) when visiting unknown destinations. Although several city guides support the provision of personalized tour recommendations to assist tourists visiting the most interesting attractions, existing tour planners only consider walking tours. Herein, we introduce eCOMPASS, a context-aware mobile application which also considers the option of using public transit for moving around. Far beyond than just providing navigational aid, eCOMPASS incorporates multimodality (i.e. time dependency) within its routing logic aiming at deriving nearoptimal sequencing of POIs along recommended tours so as to best utilize time available for sightseeing and minimize waiting time at transit stops. Further advancing the state of the art, eCOMPASS allows users to define arbitrary start/end locations(e.g. the current location of a mobile user) rather than choosing among a fixed set of locations. This paper describes the routing algorithm which comprises the core functionality of eCOMPASS and discusses the implementation details of the mobile application using the metropolitan area of Berlin (Germany) as case study
We propose a priority-based balanced routing scheme, called the priority STAR routing scheme, which leads to optimal throughput and average delay at the same time for random broadcasting and routing. In particular, the average reception delay for random broadcasting required in n1timesn2times...timesnd tori with ni=O(1), n-ary d-cubes with n=O(1), or d-dimensional hypercubes is O(d+1/(1-rho)). We also study the case where multiple communication tasks for random 1-1 routing and/or random broadcasting are executed at the same time. When a constant fraction of the traffic is contributed by broadcast requests, the average delay for random 1-1 routing required in any d-dimensional hypercube, any n-ary d-cube with n = O(1), and most n1timesn2times...timesnd tori with ni=O(1) are O(d) based on priority STAR. Our simulation results show that the priority-based balanced routing scheme considerably outperform the best previous routing schemes for these networks
We consider the problem of planning a mixed line rates (MLR) wavelength division multiplexing (WDM) transport optical network. In such networks, different modulation formats are usually employed to support the transmission at different line rates. Previously proposed planning algorithms, have used a transmission reach limit for each modulation format/line rate, mainly driven by single line rate systems. However, transmission experiments in MLR networks have shown that physical layer interference phenomena are more significant between transmissions that utilize different modulation formats. Thus, the transmission reach of a connection with a specific modulation format/line rate depends also on the other connections that copropagate with it in the network. To plan a MLR WDM network, we present routing and wavelength assignment (RWA) algorithms that take into account the adaptation of the transmission reach of each connection according to the use of the modulation formats/line rates in the network. The proposed algorithms are able to plan the network so as to alleviate interference effects, enabling the establishment of connections of acceptable quality over paths that would otherwise be prohibited
We study the problem of secure routing in wireless sensor networks where the sensors and the sink can move during the execution of remote monitoring applications and communication is not necessarily directed towards the sink. We present a new routing protocol that builds upon a collection of mechanisms so that the integrity and confidentiality of the information reported to the controlling authorities is secured. The mechanisms are simple to implement, rely only on local information and require O(1) storage per sensor. The protocol adapts to mobility and security challenges that may arise throughout the execution of the application. We take special care for wireless sensor networks that monitor dynamically changing environments and applications that require its operation for extended periods of time. APSR can detect when the current network conditions are about to change and becomes ready for adaption to the new conditions. We demonstrate how to deal with inside and outside attacks even when the network is adapting to internal and/or external events.
Optical network design problems fall in the broad category of network optimization problems. We give a short introduction on network optimization and general algorithmic techniques that can be used to solve complex and difficult network design problems. We apply these techniques to address the static Routing and Wavelength Assignment problem that is related to planning phase of a WDM optical network. We present simulation result to evaluate the performance of the proposed algorithmic solution.
[RACTI-RU1-2004-48] Boukerche, Azzedine and Nikoletseas, Sotiris, Algorithmic Design for Communication in Mobile Ad Hoc Networks, Lecture Notes in Computer Science, volume 2965, pages 235-253, chapter Performance Tools and Applications to Networked Systems, Springer Berlin / Heidelberg, ISBN 978-3-540-21945-3, 2004. [DOI]
As a result of recent significant technological advances, a new computing and communication environment, Mobile Ad Hoc Networks (MANET), is about to enter the mainstream. A multitude of critical aspects, including mobility, severe limitations and limited reliability, create a new set of crucial issues and trade-offs that must be carefully taken into account in the design of robust and efficient algorithms for these environments. The communication among mobile hosts is one among the many issues that need to be resolved efficiently before MANET becomes a commodity. In this paper, we propose to discuss the communication problem in MANET as well as present some characteristic techniques for the design, the analysis and the performance evaluation of distributed communication protocols for mobile ad hoc networks. More specifically, we propose to review two different design techniques. While the first type of protocols tries to create and maintain routing paths among the hosts, the second set of protocols uses a randomly moving subset of the hosts that acts as an intermediate pool for receiving and delivering messages. We discuss the main design choices for each approach, along with performance analysis of selected protocols.
We introduce a new model of ad-hoc mobile networks, which we call hierarchical, that are comprised of dense subnetworks of mobile users (corresponding to highly populated geographical areas, such as cities), interconnected across access ports by sparse but frequently used connections (such as highways). For such networks, we present an efficient routing protocol which extends the idea (introduced in WAE00) of exploiting the co-ordinated motion of a small part of an ad-hoc mobile network (the ``support'') to achieve very fast communication between any two mobile users of the network. The basic idea of the new protocol presented here is, instead of using a unique (large) support for the whole network, to employ a hierarchy of (small) supports (one for each city) and also take advantage of the regular traffic of mobile users across the interconnection highways to communicate between cities. We combine here theoretical analysis (average case estimations based on random walk properties) and experimental implementations (carried out using the LEDA platform) to claim and validate results showing that such a hierarchical routing approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the basic ``support'' idea presented in WAE00.
The "small world" phenomenon, i.e., the fact that the global social network is strongly connected in the sense that every two persons are inter-related through a small chain of friends, has attracted research attention and has been strongly related to the results of the social psychologist�s Stanley Milgram experiments; properties of social networks and relevant problems also emerge in peer-to-peer systems and their study can shed light on important modern network design properties. In this paper, we have experimentally studied greedy routing algorithms, i.e., algorithms that route information using "long-range" connections that function as shortcuts connecting "distant" network nodes. In particular, we have implemented greedy routing algorithms, and techniques from the recent literature in networks of line and grid topology using parallelization for increasing efficiency. To the best of our knowledge, no similar attempt has been made so far
[RACTI-RU1-2007-89] Caragiannis, Ioannis, Flamini, M and Moscardelli, L, An exponential improvement to the MST heuristic for minimum energy broadcasting in ad hoc wireless networks, in: 34th International Colloquium on Automata, Languages, and Programming (ICALP 2007), Springer, 2007.
In this paper we present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that has exponentially better approximation factor than the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most � times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ra- tio bounded by 2 ln � � 2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we signi�cantly improve previous results.
[RACTI-RU1-2009-69] Teixera, A., Costa, L, Franzi, G, Azodolmolky, Siamak, Tomkos, Ioannis, Vlachos, Kyriakos, Zsigmond, S, Cinkler, T, Tosi-Beleffi, G., Gravey, P, Lazaro, J.A, Vazquez, Carmen, Montalvo, J. and Rouzic, E.L., An Integrated View on Dynamic Monitoring and Compensation for Optical Networks: From Management to Physical Layer, in: Springer: Journal on Photonic Network Communications, volume 18, number 2, pages 191-210, 2009.
Avertical perspective, ranging from management and routing to physical layer options, concerning dynamic network monitoring and compensation of impairments (M&C),is given.Feasibility, reliability,and performance improvements on reconfigurable transparent networksare expected to arise from the consolidated assessment of network management and control specifications, as a more accurate evaluation of available M&C techniques. In the network layer,physical parameters aware algorithms are foreseen to pursue reliable network performance. In the physical layer, some new M&C methods were developed and rating of the state-of-the-art reported in literature is given. Optical monitoring implementation and viability is discussed.
[RACTI-RU1-2001-9] Chatzigiannakis, Ioannis, Nikoletseas, Sotiris and Spirakis, Paul, Analysis of an Innovative and Efficient Communication Strategy for Hierarchical Ad-hoc Mobile Networks, in: 8th Panhellenic Conference on Informatics (PCI), pages 10-19, 2001.
We introduce a new model of ad-hoc mobile networks, which we call hierarchical, that are comprised of dense subnetworks of mobile users (corresponding to highly populated geographical areas), interconnected across access ports by sparse but frequently used connections. To implement communication in such a case, a possible solution would be to install a very fast (yet limited) backbone interconnecting such highly populated mobile user areas, while employing a hierarchy of (small) supports (one for each lower level site). This fast backbone provides a limited number of access ports within these dense areas of mobile users. We combine here theoretical analysis (average case estimations based on random walk properties) to claim and validate results showing that such a hierarchical routing approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the basic ``support'' idea presented in [WAE00,DISC01].
[RACTI-RU1-2003-25] Koutsoupias, Elias, Mavronicolas, Marios and Spirakis, Paul, Approximate Equilibria and Ball Fusion, in: Theory of Computing Systems, volume 36, number 6, pages 683-693, ISSN 1432-4350 (Print) 1433-0490 (Onl, 2003. [DOI]
We consider selfish routing over a network consisting of m parallellinks through which $n$ selfish users route their traffic trying tominimize their own expected latency. We study the class of mixedstrategies in which the expected latency through each link is at mosta constant multiple of the optimum maximum latency had globalregulation been available. For the case of uniform links it is knownthat all Nash equilibria belong to this class of strategies. We areinterested in bounding the coordination ratio (or price of anarchy) ofthese strategies defined as the worst-case ratio of the maximum (overall links) expected latency over the optimum maximum latency. The loadbalancing aspect of the problem immediately implies a lower boundO(ln m ln ln m) of the coordinationratio. We give a tight (up to a multiplicative constant) upper bound.To show the upper bound, we analyze a variant of the classical ballsand bins problem, in which balls with arbitrary weights are placedinto bins according to arbitrary probability distributions. At theheart of our approach is a new probabilistic tool that we call ballfusion; this tool is used to reduce the variant of the problem whereballs bear weights to the classical version (with no weights). Ballfusion applies to more general settings such as links with arbitrarycapacities and other latency functions.
[RACTI-RU1-2006-43] Caragiannis, Ioannis, Kaklamanis, Christos and Persiano, Giuseppe, Approximation Algorithms for Path Coloring in Trees, The study of the path coloring problem is motivated by the alloc, volume 3484/2006, pages 74-96, chapter Efficient Approximation and Online Algorithms, Springer, 2006. [DOI]
The study of the path coloring problem is motivated by the allocation of optical bandwidth to communication requests in all-optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter-receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state-of-the-art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication minimizing the total number of wavelengths used. This is known as the wavelength routing problem. In the case where the underlying network is a tree, it is equivalent to the path coloring problem. We survey recent advances on the path coloring problem in both undirected and bidirected trees. We present hardness results and lower bounds for the general problem covering also the special case of sets of symmetric paths (corresponding to the important case of symmetric communication). We give an overview of the main ideas of deterministic greedy algorithms and point out their limitations. For bidirected trees, we present recent results about the use of randomization for path coloring and outline approximation algorithms that find path colorings by exploiting fractional path colorings. Also, we discuss upper and lower bounds on the performance of on-line algorithms.
We present a new architecture for bufferless, asynchronous all-optical self-routing network combining an efficient physical layer structure and conflict-preventing signaling protocol for providing lossless communication with optimum resource utilization and QoS differentiation.
We present a 40 Gb/s asynchronous self-routing network and node architecture that exploits bit and packet level optical signal processing to perform synchronization, forwarding and switching. Optical packets are self-routed on a hop-by-hop basis through the network by using stacked optical tags, each representing a specific optical node. Each tag contains control signals for configuring the switching matrix and forwarding each packet to the appropriate outgoing link and onto the next hop. Physical layer simulations are performed, modeling each optical subsystem of the node showing acceptable signal quality and Bit Error Rates. Resource reservationbased signaling algorithms are theoretically modeled for the control plane capable of providing high performance in terms of blocking probability and holding time.
[RACTI-RU1-2007-70] Chatzigiannakis, Ioannis and Nikoletseas, Sotiris, Combined Data Propagation and Energy Management in Wireless Sensor Networks, chapter Algorithms and Protocols for Wireless Ad hoc and Sensor networks, Wiley and Sons, 2007.
This chapter aims at presenting certain important aspects of the design of lightweight, event-driven algorithmic solutions for data dissemination in wireless sensor networks that provide support for reliable, efficient and concurrency-intensive operation. We wish to emphasize that efficient solutions at several levels are needed, e.g.~higher level energy efficient routing protools and lower level power management schemes. Furthermore, it is important to combine such different level methods into integrated protocols and approaches. Such solutions must be simple, distributed and local. Two useful algorithmic design principles are randomization (to trade-off efficiency and fault-tolerance) and adaptation (to adjust to high network dynamics towards improved operation). In particular, we provide a) a brief description of the technical specifications of state-of-the-art sensor devices b) a discussion of possible models used to abstract such networks, emphasizing heterogeneity, c) some representative power management schemes, and d) a presentation of some characteristic protocols for data propagation. Crucial efficiency properties of these schemes and protocols (and their combinations, in some cases) are investigated by both rigorous analysis and performance evaluations through large scale simulations.
[RACTI-RU1-2010-72] Amaxilatis, Dimitrios, Chatzigiannakis, Ioannis, Koninis, Christos and Pyrgelis, Apostolos, Component Based Clustering in Wireless Sensor Networks, number abs/1105.3864, 2010.
Clustering is an important research topic for wireless sensor networks (WSNs). A large variety of approaches has been presented focusing on di erent performance metrics. Even though all of them have many practical applications, an ex- tremely limited number of software implementations is avail- able to the research community. Furthermore, these very few techniques are implemented for speci c WSN systems or are integrated in complex applications. Thus it is very difficult to comparatively study their performance and almost impos- sible to reuse them in future applications under a di erent scope. In this work we study a large body of well estab- lished algorithms. We identify their main building blocks and propose a component-based architecture for developing clustering algorithms that (a) promotes exchangeability of algorithms thus enabling the fast prototyping of new ap- proaches, (b) allows cross-layer implementations to realize complex applications, (c) o ers a common platform to com- paratively study the performance of di erent approaches, (d) is hardware and OS independent. We implement 5 well known algorithms and discuss how to implement 11 more. We conduct an extended simulation study to demonstrate the faithfulness of our implementations when compared to the original implementations. Our simulations are at very large scale thus also demonstrating the scalability of the original algorithms beyond their original presentations. We also conduct experiments to assess their practicality in real WSNs. We demonstrate how the implemented clustering algorithms can be combined with routing and group key es- tablishment algorithms to construct WSN applications. Our study clearly demonstrates the applicability of our approach and the bene ts it o ers to both research & development communities.
In this article, we present a detailed performance evaluation of a hybrid optical switching (HOS) architecture called Overspill Routing in Optical Networks (ORION). The ORION architecture combines (optical) wavelength and (electronic) packet switching, so as to obtain the individual advantages of both switching paradigms. In particular, ORION exploits the possible insertions/extractions, to reduce the necessary interfaces, do not deteriorate performance and thus the use of traffic concentrators assure ORION�s economic viability. idle periods of established lightpaths to transmit packets destined to the next common node, or even directly to their common end-destination. Depending on whether all lightpaths are allowed to simultaneously carry and terminate overspill traffic or overspill is restricted to a sub-set of wavelengths, the architecture limits itself to constrained or un-constrained ORION. To evaluate both cases, we developed an extensive network simulator where the basic features of the ORION architectureweremodeled, including suitable edge/core node switches and load-varying sources to simulate overloading traffic conditions. Further, we have assessed various aspects of the ORION architecture including two basic routing/forwarding policies and various buffering schemes. The complete network study shows that ORION can absorb temporal traffic overloads, as intended, provided sufficient buffering is present.We also demonstrate that the restriction of simultaneous packet
[RACTI-RU1-2004-57] Kalyvas, M, Yiannopoulos, K., Houbavlis, T. and Avramopoulos, Hercules, Control Signal Generation From Flag Pulses to Drive All-Optical Gates, in: Photonics Technology Letters, IEEE, volume 16, number 4, pages 1122-1124, 2004. [DOI]
All-optical gate control signal generation is demonstrated from flag pulses, using a Fabry–P{\'e}rot filter followed by a semiconductor optical amplifier. Ten control pulses are generated from a single flag pulse having less than 0.45-dB amplitude modulation. By doubling or tripling the number of flag pulses, the number of control pulses increases approximately by a factor of two or three. The circuit can control the switching state of all-optical switches, on a packet-by-packet basis, and can be used for nontrivial network functionalities such us self-routing.
[RACTI-RU1-2009-127] Patroumpa, Dimitra, Design, Implementation and Experimental Evaluation of Data Collection Protocols in Wireless Sensor Networks with Mobile Sinks, Computer Engineering and Informatics Department , University of Patras, 2009.
Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their inveronment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. Each device has limited computational and energy resources, thus a basic issue in the applicastions of wireless sensor networks is the low energy consumption and hence, the maximization of the network lifetime. The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays. In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, a graph formation phase is executed by the sink during the initialization: the network area is partitioned in equal square regions, where the sink, pauses for a certain amount of time, during the network traversal, in order to collect data. We propose two network traversal methods, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region.Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink data transmissions only. We evaluate our methods via simulation, in diverse network settings and comparatively to related state of the art solutions. Our findings demonstrate significant latency and energy consumption improvements, compared to previous research.
[RACTI-RU1-2008-78] Kinalis, Athanasios, Desing, simulation and evaluation of energy efficient algorithms for wireless sensor networks, 2008.
Wireless sensor networks are comprised of a vast number of devices, situated in an area of interest that self organize in a structureless network, in order to monitor/record/measure an environmental variable or phenomenon and subsequently to disseminate the data to the control center. Here we present research focused on the development, simulation and evaluation of energy efficient algorithms, our basic goal is to minimize the energy consumption. Despite technology advances, the problem of energy use optimization remains valid since current and emerging hardware solutions fail to solve it. We aim to reduce communication cost, by introducing novel techniques that facilitate the development of new algorithms. We investigated techniques of distributed adaptation of the operations of a protocol by using information available locally on every node, thus through local choices we improve overall performance. We propose techniques for collecting and exploiting limited local knowledge of the network conditions. In an energy efficient manner, we collect additional information which is used to achieve improvements such as forming energy efficient, low latency and fault tolerant paths to route data. We investigate techniques for managing mobility in networks where movement is a characteristic of the control center as well as the sensors. We examine methods for traversing and covering the network field based on probabilistic movement that uses local criteria to favor certain areas. The algorithms we develop based on these techniques operate a) at low level managing devices, b) on the routing layer and c) network wide, achieving macroscopic behavior through local interactions. The algorithms are applied in network cases that differ in density, node distribution, available energy and also in fundamentally different models, such as under faults, with incremental node deployment and mobile nodes. In all these settings our techniques achieve significant gains, thus distinguishing their value as tools of algorithmic design.
Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three facets of direct routing: (i) Algorithms. We present a polynomial time greedy algorithm for arbitrary direct routing problems whch is worst-case optimal, i.e., there exist instances for which no direct routing algorithm is better than the greedy. We apply variants of this algorithm to commonly used network topologies. In particular, we obtain near-optimal routing time using for the tree and d-dimensional mesh, given arbitrary sources and destinations; for the butterfly and the hypercube, the same result holds for random destinations. (ii) Complexity. By a reduction from Vertex Coloring, we show that Direct Routing is inapproximable, unless P=NP. (iii) Lower Bounds for Buffering. We show the existence of routing problems which cannot be solved efficiently with direct routing. To solve these problems, any routing algorithm needs buffers. We give nontrivial lower bounds on such buffering requirements for general routing algorithms.
Peer-to-Peer (P2P) search requires intelligent decisions for query routing: selecting the best peers to which a given query, initiated at some peer, should be forwarded for retrieving additional search results. These decisions are based on statistical summaries for each peer, which are usually organized on a per-keyword basis and managed in a distributed directory of routing indices. Such architectures disregard the possible correlations among keywords. Together with the coarse granularity of per-peer summaries, which are mandated for scalability, this limitation may lead to poor search result quality. This paper develops and evaluates two solutions to this problem, sk-STAT based on single-key statistics only, and mk-STAT based on additional multi-key statistics. For both cases, hash sketch synopses are used to compactly represent a peer's data items and are efficiently disseminated in the P2P network to form a decentralized directory. Experimental studies with Gnutella and Web data demonstrate the viability and the trade-offs of the approaches.
[RACTI-RU1-2009-52] Huc, F, Jarry, A., Leone, Pierre, Rolim, Jose, Moraru, Luminita and Nikoletseas, Sotiris, Early Obstacle Detection and Avoidance for All to All Traffic Pattern in Wireless Sensor Networks, in: 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2009), Springer Verlag, Rhodes, Greece, 2009.
This paper deals with early obstacles recognition in wireless sensor networks under various traffic patterns. In the presence of obstacles, the efficiency of routing algorithms is increased by voluntarily avoiding some regions in the vicinity of obstacles, areas which we call dead-ends. In this paper, we first propose a fast convergent routing algorithm with proactive dead-end detection together with a formal definition and description of dead-ends. Secondly, we present a generalization of this algorithm which improves performances in all to many and all to all traffic patterns. In a third part we prove that this algorithm produces paths that are optimal up to a constant factor of 2�+1. In a fourth part we consider the reactive version of the algorithm which is an extension of a previously known early obstacle detection algorithm. Finally we give experimental results to illustrate the efficiency of our algorithms in different scenarios.
We investigate the Vehicle Routing Problem with Time Windows (VRPTW) under an eco-friendly framework that demands the delivery of balanced and compact customer clusters. We present a new approach consisting of three major phases: (i) a first clustering of customers with compatible time windows; (ii) a second clustering of customers with close geographic proximity based on various methods (natural cuts, KaHIP, quad trees); (iii) a refinement phase that either splits a cluster into smaller ones, or merges clusters to form a bigger compact cluster. Our approach turns out to be beneficial when used in an on-line environment, where changes to the initial tour are requested (add a new customer to the tour or drop some customers). The new method serves as a warm starting point for re-evaluating and further optimizing the solution of VRPTW. Experiments with real data sets demonstrate that our approach compares favorably with standard approaches that start from a basic (cold) solution.
[RACTI-RU1-2010-69] Angelopoulos, Constantinos Marios, Efficient Data Collection Protocols for Wireless Sensor Networks, Computer Engineering and Informatics Department , University of Patras, 2010.
In this thesis we investigate the problems of data routing and data collection in wireless sensor networks characterised by intense and higly diverse mobility. We propose a set of protocols that takes exploits the motion of the sensors in order to inform the sink about the network topology. We experimentally evaluate these protocolls in a wide range of topologies, including both homogeneous and heterogeneous ones. We also investigate random walks as simple motion strategies for mobile sinks that perform data collection from static WSN's. We propose three new random walks that improve latency compared to already known ones, as well as a new metric called Proximity Variation. This metric captures the different way each random walks traverses the network area.
We examine a task scheduling and data migration problem for grid networks, which we refer to as the Data Consolidation (DC) problem. DC arises when a task concurrently requests multiple pieces of data, possibly scattered throughout the grid network, that have to be present at a selected site before the task�s execution starts. In such a case, the scheduler and the data manager must select (i) the data replicas to be used, (ii) the site where these data will be gathered for the task to be executed, and (iii) the routing paths to be followed; this is assuming that the selected datasets are transferred concurrently to the execution site. The algorithms or policies for selecting the data replicas, the data consolidating site and the corresponding paths comprise a Data Consolidation scheme. We propose and experimentally evaluate several DC schemes of polynomial number of operations that attempt to estimate the cost of the concurrent data transfers, to avoid congestion that may appear due to these transfers and to provide fault tolerance. Our simulation results strengthen our belief that DC is an important problem that needs to be addressed in the design of data grids, and can lead, if performed efficiently, to significant benefits in terms of task delay, network load and other performance parameters.
[RACTI-RU1-2012-15] Angelopoulos, Constantinos Marios, Nikoletseas, Sotiris, Raptis, Theofanis, Raptopoulos, Christoforos and Vasilakis, Filippos, Efficient energy management in wireless rechargeable sensor networks, in: 15th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (IEEE MSWiM) 2012, pages 309-316, 15th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (IEEE MSWiM) 2012, Paphos, Cyprus, 2012.
Through recent technology advances in the eld of wireless energy transmission, Wireless Rechargeable Sensor Networks (WRSN) have emerged. In this new paradigm for WSNs a mobile entity called Mobile Charger (MC) traverses the network and replenishes the dissipated energy of sensors. In this work we rst provide a formal de nition of the charging dispatch decision problem and prove its computational hardness. We then investigate how to optimize the tradeo s of several critical aspects of the charging process such as a) the trajectory of the charger, b) the di erent charging policies and c) the impact of the ratio of the energy the MC may deliver to the sensors over the total available energy in the network. In the light of these optimizations, we then study the impact of the charging process to the network lifetime for three characteristic underlying routing protocols; a greedy protocol, a clustering protocol and an energy balancing protocol. Finally, we propose a Mobile Charging Protocol that locally adapts the circular trajectory of the MC to the energy dissipation rate of each sub-region of the network. We compare this protocol against several MC trajectories for all three routing families by a detailed experimental evaluation. The derived ndings demonstrate signi cant performance gains, both with respect to the no charger case as well as the di erent charging alternatives; in particular, the performance improvements include the network lifetime, as well as connectivity, coverage and energy balance properties.
[RACTI-RU1-2011-81] Christodoulopoulos, Konstantinos, Tomkos, Ioannis and Varvarigos, Emmanouel, Elastic Bandwidth Allocation in Flexible OFDM-based Optical Networks, in: Journal of Lightwave Technology, volume 29, number 9, pages 1354-1366, 2011.
Orthogonal Frequency Division Multiplexing (OFDM) has recently been proposed as a modulation technique for optical networks, because of its good spectral efficiency, flexibility, and tolerance to impairments. We consider the planning problem of an OFDM optical network, where we are given a traffic matrix that includes the requested transmission rates of the connections to be served. Connections are provisioned for their requested rate by elastically allocating spectrum using a variable number of OFDM subcarriers and choosing an appropriate modulation level, taking into account the transmission distance. We introduce the Routing, Modulation Level and Spectrum Allocation (RMLSA) problem, as opposed to the typical Routing and Wavelength Assignment (RWA) problem of traditional WDM networks, prove that is also NP-complete and present various algorithms to solve it. We start by presenting an optimal ILP RMLSA algorithm that minimizes the spectrum used to serve the traffic matrix, and also present a decomposition method that breaks RMLSA into its two substituent subproblems, namely, (i) routing and modulation level, and (ii) spectrum allocation (RML+SA), and solves them sequentially. We also propose a heuristic algorithm that serves connections one-by-one and use it to solve the planning problem by sequentially serving all the connections in the traffic matrix. In the sequential algorithm, we investigate two policies for defining the order in which connections are considered. We also use a simulated annealing meta-heuristic to obtain even better orderings. We examine the performance of the proposed algorithms through simulation experiments and evaluate the spectrum utilization benefits that can be obtained by utilizing OFDM elastic bandwidth allocation, when compared to a traditional WDM network.
In this work we study energy efficient routing strategies for wireless ad-hoc networks. In this kind of networks, energy is a scarce resource and its conservation and efficient use is a major issue. Our strategy follows the multi-cost routing approach, according to which a cost vector of various parameters is assigned to each link. The parameters of interest are the number of hops on a path, and the residual energy and the transmission power of the nodes on the path. These parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. We evaluate the routing algorithms proposed in a number of scenarios, with respect to energy consumption, throughput and other performance parameters of interest. From the experiments conducted we conclude that routing algorithms that take into account energy related parameters, increase the lifetime of the network, while achieving better performance than other approaches, such as minimum hop routing.
[RACTI-RU1-2004-17] Chatzigiannakis, Ioannis, Kaltsa, Elena and Nikoletseas, Sotiris, Evaluating the Effect of User Mobility and User Density on the Performance of Ad-hoc Mobile Networks, in: Wireless Communications and Mobile Computing (WMC), volume 4, number 6, pages 1-13, 2004. [DOI]
In this paper, we demonstrate the significant impact of (a) the mobility rate and (b) the user density on the performance of routing protocols in ad-hoc mobile networks. In particular, we study the effect of these parameters on two different approaches for designing routing protocols: (a) the route creation and maintenance approach and (b) the support approach that forces few hosts to move, acting as helpers for message delivery. We study one representative protocol for each approach, i.e. AODV for the first approach and RUNNERS for the second. We have implemented the two protocols and performed a large scale and detailed simulation study of their performance. The main findings are: the AODV protocol behaves well in networks of high user density and low mobility rate, while its performance drops for sparse networks of highly mobile users. On the other hand, the RUNNERS protocol seems to tolerate well (and in fact benefit from) high mobility rates and low densities.
[RACTI-RU1-2011-62] Azodolmolky, Siamak, Perell�, Jordi, Angelou, Marianna, Agraz, Fernando, Velasco, Luis, Spadaro, Salvatore, Pointurier, Yvan, Francescon, A., Saradhi, Chava Vijaya, Kokkinos, Panagiotis, Varvarigos, Emmanouel, Zahr, Sawsan Al, Gagnaire, Maurice, Gunkel, Matthias, Klonidis, Dimitris and Tomkos, Ioannis, Experimental demonstration of an impairment aware network planning and operation tool for transparent/translucent optical networks, in: Journal of Lightwave Technology, volume 29, number 4, pages 439-448, 2011.
Core optical networks using reconfigurable optical switches and tunable lasers appear to be on the road towards widespread deployment and could evolve to all-optical mesh networks in the coming future. Considering the impact of physical layer impairments in the planning and operation of all-optical (and translucent) networks is the main focus of the DICONET project. The impairment aware network planning and operation tool (NPOT) is the main outcome of DICONET project, which is explained in detail in this paper. The key building blocks of the NPOT, consisting of network description repositories, the physical layer performance evaluator, the impairment aware routing and wavelength assignment engines, the component placement modules, failure handling and the integration of NPOT in the control plane are the main contributions of this work. Besides, the experimental result of DICONET proposal for centralized and distributed control plane integration schemes and the performance of the failure handling in terms of restoration time is presented in this work.
[RACTI-RU1-2005-41] Kaporis, Alexis, Kirousis, Lefteris, Politopoulou, E. I. and Spirakis, Paul, Experimental Results for Stackelberg Scheduling Strategies, in: 4th International Workshop on Efficient and Experimental Algorithms (WEA 2005), pages 77-88, 2005. [DOI]
In large scale networks users often behave selfishly trying to minimize their routing cost. Modelling this as a noncooperative game, may yield a Nash equilibrium with unboundedly poor network performance. To measure this inefficacy, the Coordination Ratio or Price of Anarchy (PoA) was introduced. It equals the ratio of the cost induced by the worst Nash equilibrium, to the corresponding one induced by the overall optimum assignment of the jobs to the network. On improving the PoA of a given network, a series of papers model this selfish behavior as a Stackelberg or Leader-Followers game. We consider random tuples of machines, with either linear or M/M/1 latency functions, and PoA at least a tuning parameter c. We validate a variant (NLS) of the Largest Latency First (LLF) Leaderrsquos strategy on tuples with PoA ge c. NLS experimentally improves on LLF for systems with inherently high PoA, where the Leader is constrained to control low portion agr of jobs. This suggests even better performance for systems with arbitrary PoA. Also, we bounded experimentally the least Leaderrsquos portion agr0 needed to induce optimum cost. Unexpectedly, as parameter c increases the corresponding agr0 decreases, for M/M/1 latency functions. All these are implemented in an extensive Matlab toolbox.
[RACTI-RU1-2003-7] Gairing, Martin, Lucking, Thomas, Mavronicolas, Marios, Monien, Burkhart and Spirakis, Paul, Extreme Nash Equilibria, in: 8th Italian Conference on Theoretical Computer Science (ICTCS 2003), pages 1-20, Springer Berlin / Heidelberg, University Center Bertinoro, Italy, 2003. [DOI]
We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user routes its traffic on links that minimize its expected latency cost. Our structural results provide substantial evidence for the Fully Mixed Nash Equilibrium Conjecture, which states that the worst Nash equilibrium is the fully mixed Nash equilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria and that under a certain condition, the social cost of any Nash equilibrium is within a factor of 6 + epsi, of that of the fully mixed Nash equilibrium, assuming that link capacities are identical. Our complexity results include hardness, approximability and inapproximability ones. Here we show, that for identical link capacities and under a certain condition, there is a randomized, polynomial-time algorithm to approximate the worst social cost within a factor arbitrarily close to 6 + epsi. Furthermore, we prove that for any arbitrary integer k > 0, it is -hard to decide whether or not any given allocation of users to links can be transformed into a pure Nash equilibrium using at most k selfish steps. Assuming identical link capacities, we give a polynomial-time approximation scheme (PTAS) to approximate the best social cost over all pure Nash equilibria. Finally we prove, that it is -hard to approximate the worst social cost within a multiplicative factor . The quantity is the tight upper bound on the ratio of the worst social cost and the optimal cost in the model of identical capacities.
Geographic routing is becoming the protocol of choice for many sensor network applications. Some very efficient geographic routing algorithms exist, however they require a preliminary planarization of the communication graph. Planarization induces overhead which makes this approach not optimal when lightweight protocols are required. On the other hand, georouting algorithms which do not rely on planarization have fairly low success rates and either fail to route messages around all but the simplest obstacles or have a high topology control overhead (e.g. contour detection algorithms). In this entry we describe the GRIC algorithm which was designed to overcome some of those limitations. The GRIC algorithm was proposed in [PN07a]. It is the first lightweight and efficient on demand (i.e. all-to-all) geographic routing algorithm which does not require planarization, has almost 100% delivery rates (when no obstacles are added), and behaves well in the presence of large communication blocking obstacles.
[RACTI-RU1-2009-94] Manousakis, Kostas, Christodoulopoulos, Konstantinos and Varvarigos, Emmanouel, Impairment-Aware Offline RWA for Transparent Optical Networks, in: INFOCOM, pages 1557-1565, 2009.
We consider the offline version of the routing and wavelength assignment (RWA) problem in transparent all-optical networks. In such networks and in the absence of regenerators, the signal quality of transmission degrades due to physical layer impairments. We initially present an algorithm for solving the static RWA problem based on an LP relaxation formulation that tends to yield integer solutions. To account for signal degradation due to physical impairments, we model the effects of the path length, the path hop count, and the interference among ligthpaths by imposing additional (soft) constraints on RWA. The objective of the resulting optimization problem is not only to serve the connection requests using the available wavelengths, but also to minimize the total accumulated signal degradation on the selected lightpaths. Our simulation studies indicate that the proposed RWA algorithms select the lightpaths for the requested connections so as to avoid impairment generating sources, thus dramatically reducing the overall physical-layer blocking when compared to RWA algorithms that do not account for impairments.
In this work we study the implementation of multicost rout- ing in a distributed way in wireless mobile ad hoc networks. In contrast to traditional single-cost routing, where each path is characterized by a scalar, in multicost routing a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calcu- lated. These parameters are combined in various optimiza- tion functions, corresponding to different routing algorithms, for selecting the optimal path. Up until now the performance of multicost and multi-constrained routing in wireless ad hoc networks has been evaluated either at a theoretical level or by assuming that nodes are static and have full knowledge of the network topology and nodes� state. In the present paper we assess the performance of multicost routing based on energy-related parameters in mobile ad hoc networks by embedding its logic in the Dynamic Source Routing (DSR) algorithm, which is a well-known fully distributed routing algorithm. We use simulations to compare the performance of the multicost-DSR algorithm to that of the original DSR algorithm and examine their behavior under various node mobility scenarios. The results confirm that the multicost- DSR algorithm improves the performance of the network in comparison to the original DSR algorithm in terms of energy efficiency. The multicost-DSR algorithm enhances the performance of the network not only by reducing energy consumption overall in the network, but also by spreading energy consumption more uniformly across the network, pro longing the network lifetime and reducing the packet drop probability. Furthermore the delay suffered by the packets reaching their destination for the case of the multicost-DSR algorithm is shown to be lower than in the case of the orig inal DSR algorithm.
[RACTI-RU1-2011-58] Christodoulopoulos, Konstantinos, Kokkinos, Panagiotis and Varvarigos, Emmanouel, Indirect and Direct Multicost Algorithms to Online Impairment-Aware RWA, in: IEEE/ACM Transactions on Networking, 2011.
We consider the online impairment-aware routing and wavelength assignment (IA-RWA) problem in transparent WDM networks. To serve a new connection, the online algorithm, in addition to finding a route and a free wavelength (a lightpath), has to guarantee its transmission quality, which is affected by physical-layer impairments. Due to interference effects, the establishment of the new lightpath affects and is affected by the other lightpaths. We present two multicost algorithms that account for the actual current interference among lightpaths, as well as for other physical effects, performing a cross-layer optimization between the network and physical layers. In multicost routing, a vector of cost parameters is assigned to each link, from which the cost vectors of the paths are calculated. The first algorithm utilizes cost vectors consisting of impairment-generating source parameters, so as to be generic and applicable to different physical settings. These parameters are combined into a scalar cost that indirectly evaluates the quality of candidate lightpaths. The second algorithm uses specific physical-layer models to define noise variance-related cost parameters, so as to directly calculate the -factor of candidate lightpaths. The algorithms find a set of so-called nondominated paths to serve the connection in the sense that no path is better in the set with respect to all cost parameters. To select the lightpath, we propose various optimization functions that correspond to different IA-RWA algorithms. The proposed algorithms combine the strength of multicost optimization with low execution times, making them appropriate for serving online connections
[RACTI-RU1-2007-56] Develder, C., De Leenheer, M., Dhoedt, B., Christodoulopoulos, Konstantinos and Varvarigos, Emmanouel, Job Demand Models For Optical Grid Research, in: 11th Conference on Optical Network Design and Modelling (ONDM), pages 127-136, 2007.
This paper presents results from the IST Phosphorus project that studies and implements an optical Grid test-bed. A significant part of this project addresses scheduling and routing algorithms and dimensioning problems of optical grids. Given the high costs involved in setting up actual hardware implementations, simulations are a viable alternative. In this paper we present an initial study which proposes models that reflect real-world grid application traffic characteristics, appropriate for simulation purposes. We detail several such models and the corresponding process to extract the model parameters from real grid log traces, and verify that synthetically generated jobs provide a realistic approximation of the real-world grid job submission process.
In this work we study the combination of multicost routing and adjustable transmission power in wireless ad hoc networks, so as to obtain dynamic energy- and interference-efficient routes to optimize network performance. In multi-cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calculated. Only at the end these parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. The multi-cost routing problem is a generalization of the multi-constrained problem, where no constraints exist, and is also significantly more powerful than single-cost routing. Since energy is an important limitation of wireless communications, the cost parameters considered are the number of hops, the interference caused, the residual energy and the transmission power of the nodes on the path; other parameters could also be included, as desired. We assume that nodes can use power control to adjust their transmission power to the desired level. The experiments conducted show that the combination of multicost routing and adjustable transmission power can lead to reduced interference and energy consumption, improving network performance and lifetime.
[RACTI-RU1-2005-18] Chatzigiannakis, Ioannis, Mylonas, Georgios and Nikoletseas, Sotiris, jWebDust: A Java-based Generic Application Environment for Wireless Sensor Networks, in: 1st IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS 2005), pages 376-386, Springer Verlag, IEEE/ACM, Marina Del Rey, CA, USA, 2005. [DOI]
Wireless sensor networks can be very useful in applications that require the detection of crucial events, in physical environments subjected to critical conditions, and the propagation of data reporting their realization to a control center. In this paper we propose jWebDust, a generic and modular application environment for developing and managing applications that are based on wireless sensor networks. Our software architecture provides a range of services that allow to create customized applications with minimum implementation effort that are easy to administrate. We move beyond the ?networking-centric? view of sensor network research and focus on how the end user (administrator, control center supervisor, etc.) will visualize and interact with the system. We here present its open architecture, the most important design decisions, and discuss its distinct features and functionalities. jWebDust allows heterogeneous components to interoperate (real world sensor networks will rarely be homogeneous) and allows the integrated management and control of multiple such networks by also defining web-based mechanisms to visualize the network state, the results of queries, and a means to inject queries in the network. The architecture also illustrates how existing protocols for various services can interoperate in a bigger framework - such as the tree construction, query routing, etc.
A key problem in Grid networks is how to efficiently manage the available infrastructure, in order to satisfy user requirements and maximize resource utilization. This is in large part influenced by the algorithms responsible for the routing of data and the scheduling of tasks. In this paper,wepresent several multi-cost algorithms for the joint scheduling of the communication and computation resources that will be used by a Grid task. We propose a multi-cost scheme of polynomial complexity that performs immediate reservations and selects the computation resource to execute the task and determines the path to route the input data. Furthermore, we introduce multi-cost algorithms that perform advance reservations and thus also find the starting times for the data transmission and the task execution. We initially present an optimal scheme of non-polynomial complexity and by appropriately pruning the set of candidate paths we also give a heuristic algorithm of polynomial complexity. Our performance results indicate that in a Grid network in which tasks are either CPU- or data-intensive (or both), it is beneficial for the scheduling algorithm to jointly consider the computational and communication problems. A comparison between immediate and advance reservation schemes shows the trade-offs with respect to task blocking probability, end-to-end delay and the complexity of the algorithms.
We propose a class of novel energy-efficient multi-cost routing algorithms for wireless mesh networks, and evaluate their performance. In multi-cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calculated using appropriate operators. In the end these parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. We evaluate the performance of the proposed energy-aware multi-cost routing algorithms under two models. In the network evacuation model, the network starts with a number of packets that have to be transmitted and an amount of energy per node, and the objective is to serve the packets in the smallest number of steps, or serve as many packets as possible before the energy is depleted. In the dynamic one-to-one communication model, new data packets are generated continuously and nodes are capable of recharging their energy periodically, over an infinite time horizon, and we are interested in the maximum achievable steady-state throughput, the packet delay, and the energy consumption. Our results show that energy-aware multi-cost routing increases the lifetime of the network and achieves better overall network performance than other approaches.
In this work we study the combination of multicost routing and adjustable transmission power in wireless ad-hoc networks, so as to obtain dynamic energy and interference-efficient routes to optimize network performance. In multi-cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calcu- lated. Only at the end are these parameters combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. The multi-cost routing problem is a generalization of the multi-constrained problem, where no constraints exist, and is also significantly more powerful than single- cost routing. Since energy is an important limitation of wireless communications, the cost parameters consid ered are the number of hops, the interference caused, the residual energy and the transmission power of the nodes on the path; other parameters could also be in cluded, as desired.We assume that nodes can use power control to adjust their transmission power to the desired level. The experiments conducted show that the com bination of multi-cost routing and adjustable transmis sion power can lead to reduced interference and energy consumption, improving network performance and life- time.
In this work we study the dynamic one-to-one communica- tion problem in energy- and capacity-constrained wireless ad-hoc net- works. The performance of such networks is evaluated under random traffic generation and continuous energy recharging at the nodes over an infinite-time horizon.We are interested in the maximum throughput that can be sustained by the network with the node queues being finite and in the average packet delay for a given throughput. We propose a multicost energy-aware routing algorithm and compare its performance to that of minimum-hop routing. The results of our experiments show that gener- ally the energy-aware algorithm achieves a higher maximum throughput than the minimum-hop algorithm. More specifically, when the network is mainly energy-constrained and for the 2-dimensional topology consid- ered, the throughput of the proposed energy-aware routing algorithm is found to be almost twice that of the minimum-hop algorithm.
[RACTI-RU1-2006-47] Tsaggouris, George and Zaroliagis, Christos, Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications, in: 17th International Symposium Algorithms and Computation, pages 389-398, Springer-Verlag, ISAAC 2006, 2006.
We provide an improved FPTAS for multiobjective shortest paths,a fundamental (NP_hard) problem in multiobjective optimization,along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems that have important applications in QoS routing and in traffic optimization.
[RACTI-RU1-2009-129] Tsaggouris, George and Zaroliagis, Christos, Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications, in: Theory of Computing Systems, volume 45, number 1, pages 162-186, 2009. [DOI]
We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective constrained [optimal] path and non-additive shortest path, that have important applications in QoS routing and in traffic optimization. We also show how to obtain a FPTAS to a natural generalization of the weighted multicommodity flow problem with elastic demands and values that models several realistic scenarios in transportation and communication networks.
[RACTI-RU1-2008-9] Kalles, D., Kaporis, Alexis and Spirakis, Paul, Myopic Distributed Protocols for Singleton and Independent-Resource Congestion Games, in: 7th International Workshop on Experimental Algorithms (WEA 2008), pages 181-193, Springer-Verlag Berlin Heidelberg, Massachusetts, USA, 2008.
Let n atomic players be routing their unsplitable flow on mresources. When each player has the option to drop her current resource and select a better one, and this option is exercised sequentially and unilaterally, then a Nash Equilibrium (NE) will be eventually reached. Acting sequentially, however, is unrealistic in large systems. But, allowing concurrency, with an arbitrary number of players updating their resources at each time point, leads to an oscillation away from NE, due to big groups of players moving simultaneously and due to nonsmooth resource cost functions. In this work, we validate experimentally simple concurrent protocols that are realistic, distributed and myopic yet are scalable, require only information local at each resource and, still, are experimentally shown to quickly reach a NE for a range of arbitrary cost functions.
[RACTI-RU1-2003-14] Triantafillou, Peter, Ntarmos, Nikos, Nikoletseas, Sotiris and Spirakis, Paul, NanoPeer Networks and P2P Worlds, in: 3rd International Conference on Peer-to-Peer Computing (P2P 2003), pages 40-46, IEEE Computer Society, 2003. [DOI]
We present the NanoPeers architecture paradigm, a peer-to-peer network of lightweight devices, lacking all or most of the capabilities of their computer-world counterparts. We identify the problems arising when we apply current routing and searching methods to this nano-world, and present some initial solutions, using a case study of a sensor network instance; Smart Dust. Furthermore, we propose the P2P Worlds framework as a hybrid P2P architecture paradigm, consisting of cooperating layers of P2P networks, populated by computing entities with escalating capabilities. Our position is that (i) experience gained through research and experimentation in the field of P2P computing, can be indispensable when moving down the stair of computing capabilities, and that (ii) the proposed framework can be the basis of numerous real-world applications, opening up several challenging research problems.
We propose local mechanisms for efficiently marking the broader network region around obstacles, for data propagation to early enough avoid them towards near-optimal routing paths. In particular, our methods perform an online identification of sensors lying near obstacle boundaries,which then appropriately emit beacon messages in the network towards establishing efficient obstacle avoidance paths. We provide a variety of beacon dissemination schemes that satisfy different trade-offs between protocol overhead and performance. Compared to greedy, face routing and trustbased methods in the state of the art, our methods achieve significantly shorter propagation paths, while introducing much lower overhead and converging faster to near-optimality.
Geographic routing scales well in sensor networks, mainly due to its stateless nature. Still, most of the algorithms are concerned with finding some path, while the optimality of the path is difficult to achieve. In this paper we are presenting a novel geographic routing algorithm with obstacle avoidance properties. It aims at finding the optimal path from a source to a destination when some areas of the network are unavailable for routing due to low local density or obstacle presence. It locally and gradually with time (but, as we show, quite fast) evaluates and updates the suitability of the previously used paths and ignores non optimal paths for further routing. By means of extensive simulations, we are comparing its performance to existing state of the art protocols, showing that it performs much better in terms of path length thus minimizing latency, space, overall traffic and energy consumption.
[RACTI-RU1-2009-105] Koutsopoulos, A, Nikoletseas, Sotiris and Rolim, Jose, Near-optimal data propagation by efficiently advertising obstacle boundaries, in: International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems, Spain, 2009.
We propose local mechanisms for efficiently marking the broader network region around obstacles, for data propagation to early enough avoid them towards near-optimal routing paths. In particular, our methods perform an online identification of sensors lying near obstacle boundaries, which then appropriately emit beacon messages in the network towards establishing efficient obstacle avoidance paths. We provide a variety of beacon dissemination schemes that satisfy different trade-offs between protocol overhead and performance. Compared to greedy, face routing and trustbased methods in the state of the art, our methods achieve significantly shorter propagation paths, while introducing much lower overhead and converging faster to near-optimality.
[RACTI-RU1-2005-70] Caragiannis, Ioannis, Galdi, C. and Kaklamanis, Christos, Network Load Games, in: 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), pages 809-818, Springer, 2005.
We study network load games, a class of routing games in networks which generalize sel{\^A}�sh routing games on networks consisting of parallel links. In these games, each user aims to route some tra{\^A}�c from a source to a destination so that the maximum load she experiences in the links of the network she occupies is minimum given the routing decisions of other users. We present results related to the existence, complexity, and price of anarchy of Pure Nash Equilibria for several network load games. As corollaries, we present interesting new statements related to the complexity of computing equilibria for sel{\^A}�sh routing games in net- works of restricted parallel links.
We consider the offline version of the routing and wavelength assignment (RWA) problem in transparent all-optical networks. In such networks and in the absence of regenerators, the signal quality of transmission degrades due to physical layer impairments. Because of certain physical effects, routing choices made for one lightpath affect and are affected by the choices made for the other lightpaths. This interference among the lightpaths is particularly difficult to formulate in an offline algorithm since, in this version of the problem, we start without any established connections and the utilization of lightpaths are the variables of the problem.We initially present an algorithm for solving the pure (without impairments) RWA problem based on a LP-relaxation formulation that tends to yield integer solutions. Then, we extend this algorithm and present two impairment-aware (IA) RWA algorithms that account for the interference among lightpaths in their formulation. The first algorithm takes the physical layer indirectly into account by limiting the impairment-generating sources. The second algorithm uses noise variance-related parameters to directly account for the most important physical impairments. The objective of the resulting cross-layer optimization problem is not only to serve the connections using a small number of wavelengths (network layer objective), but also to select lightpaths that have acceptable quality of transmission (physical layer objective). Simulations experiments using realistic network, physical layer, and traffic parameters indicate that the proposed algorithms can solve real problems within acceptable time.
[RACTI-RU1-2004-27] Chatzigiannakis, Ioannis, Kaltsa, Elena and Nikoletseas, Sotiris, On the effect of user mobility and density on the performance of ad-hoc mobile networks, in: Journal of Wireless Communications and Mobile Computing, volume 4, number 6, pages 336-341, 2004. [DOI]
In this paper we demonstrate the significant impact of (a) the mobility rate and (b) the user density on the performance of routing protocols in ad-hoc mobile networks. In particular, we study the effect of these parameters on two different approaches for designing routing protocols: (a) the route creation and maintenance approach and (b) the "support" approach, that forces few hosts to move acting as "helpers" for message delivery. We study one representative protocol for each approach, i.e., AODV for the first approach and RUNNERS for the second. We have implemented the two protocols and performed a large scale and detailed simulation study of their performance. For the first time, we study AODV (and RUNNERS) in the 3D case. The main findings are: the AODV protocol behaves well in networks of high user density and low mobility rate, while its performance drops for sparse networks of highly mobile users. On the other hand, the RUNNERS protocol seems to tolerate well (and in fact benefit from) high mobility rates and low densities. Thus, we are able to partially answer an important conjecture of [Chatzigiannakis, I et al. 2003].
In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We first show that bottleneck routing games do not suffer from Braess's paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as \Omega(n^{0.121}) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^{0.121-\eps}), for any constant \eps > 0. On the positive side, we show how to compute an almost optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all used edges. The running time is determined by the total number of paths, and is quasipolynomial when the number of paths is quasipolynomial.
[RACTI-RU1-2009-63] Monoyios, Demetris, Vlachos, Kyriakos, Tomkos, Ioannis and Angelou, Marianna, On the use of Multi-Objective Optimization Algorithms for solving the Impairment Aware- RWA problem, in: IEEE International Conference on Communications (ICC 2009), Dresden, Germany, 2009.
In future transparent optical networks, it is important to consider the impact of physical impairments in the routing and wavelengths assignment process, to achieve efficient connection provisioning. In this paper, we use classical multi- objective optimization (MOO) strategies and particularly genetic algorithms to jointly solve the impairment aware RWA (IA- RWA) problem. Fiber impairments are indirectly considered through the insertion of the path length and the number of common hops in the optimization process. It is shown that blocking is greatly improved, while the obtained solutions truly converge towards the Pareto front that constitutes the set of global optimum solutions. We have evaluated our findings, using an Q estimator tool, that calculates the signal quality of each path analytically. Index Terms RWA, Genetic Algorithm, All-Optical Networks, Multi Objective Optimization.
[RACTI-RU1-2009-118] Kokkinos, Panagiotis, Christodoulopoulos, Konstantinos, Manousakis, Kostas and Varvarigos, Emmanouel, Online RWA Based on Impairment Generating Sources, in: 28th IEEE conference on Global telecommunications, USA, 2009.
We propose and evaluate an impairment-aware multi-parametric routing and wavelength assignment algorithm for online traffic in transparent optical networks. In such networks the signal quality of transmission degrades due to physical layer impairments. In the multiparametric approach, a vector of cost parameters is assigned to each link, from which the cost vectors of candidate lightpaths are calculated. In the proposed scheme the cost vector includes impairment generating source parameters, such as the path length, the number of hops, the number of crosstalk sources and other inter-lightpath interfering parameters, so as to indirectly account for the physical layer effects. For a requested connection the algorithm calculates a set of candidate lightpaths, whose quality of transmission is validated using a function that combines the impairment generating parameters. For selecting the lightpath we propose and evaluate various optimization functions that correspond to different IA-RWA algorithms. Our performance results indicate that the proposed algorithms utilize efficiently the available resources and minimize the total accumulated signal degradation on the selected lightpaths, while having low execution times.
[RACTI-RU1-2008-72] Teimoori, Hassan, Apostolopoulos, Dimitrios, Vlachos, Kyriakos, Ware, Cedric, Petrantonakis, D., Stampoulidis, L., Avramopoulos, Hercules and Erasme, Didier, Optical logic gate aided packet switching in transparent optical networks, in: IEEE/OSA Journal of Lightwave technology, volume 26, number 13-16, pages 2848-2856, ISSN 0733-8724, 2008.
The objective of this research is to propose two new optical procedures for packet routing and forwarding in the framework of transparent optical networks. The single-wavelength label-recognition and packet-forwarding unit, which represents the central physical constituent of the switching node, is fully described in both cases. The first architecture is a hybrid opto-electronic structure relying on an optical serial-to-parallel converter designed to slow down the label processing. The remaining switching operations are done electronically. The routing system remains transparent for the packet payloads. The second architecture is an all-optical architecture and is based on the implementation of all-optical decoding of the parallelized label. The packet-forwarding operations are done optically. The major subsystems required in both of the proposed architectures are described on the basis of nonlinear effects in semiconductor optical amplifiers. The experimental results are compatible with the integration of the whole architecture. Those subsystems are a 4-bit time-to-wavelength converter, a pulse extraction circuit, a an optical wavelength generator, a 3 x 8 all-optical decoder and a packet envelope detector.
[RACTI-RU1-2010-15] Jarry, A., Leone, Pierre, Nikoletseas, Sotiris and Rolim, Jose, Optimal Data Gathering Paths and Energy Balance Mechanisms in Wireless Networks, in: DCOSS, pages 288-305, 2010.
This paper studies the data gathering problem in wireless networks, where data generated at the nodes has to be collected at a single sink. We investigate the relationship between routing optimality and fair resource management. In particular, we prove that for energy balanced data propagation, Pareto optimal routing and flow maximization are equivalent, and also prove that flow maximization is equivalent to maximizing the network lifetime. We algebraically characterize the network structures in which energy balanced data flows are maximal. Moreover, we algebraically characterize communication links which are not used by an optimal flow. This leads to the characterization of minimal network structures supporting the maximal flows. We note that energy balance, although implying global optimality, is a local property that can be computed efficiently and in a distributed manner. We suggest online distributed algorithms for energy balance in different optimal network structures and numerically show their stability in particular setting. We remark that although the results obtained in this paper have a direct consequence in energy saving for wireless networks they do not limit themselves to this type of networks neither to energy as a resource. As a matter of fact, the results are much more general and can be used for any type of network and different type of resources.
[RACTI-RU1-2011-66] Jarry, A., Leone, Pierre, Nikoletseas, Sotiris and Rolim, Jose, Optimal data gathering paths and energy-balance mechanisms in wireless networks, in: Ad Hoc Networks, volume 9, number 6, pages 1036-1048, 2011.
This paper studies the data gathering problem in wireless networks, where data generated at the nodes has to be collected at a single sink. We investigate the relationship between routing optimality and fair resource management. In particular, we prove that for energy-balanced data propagation, Pareto optimal routing and flow maximization are equivalent, and also prove that flow maximization is equivalent to maximizing the network lifetime. We algebraically characterize the network structures in which energy-balanced data flows are maximal. Moreover, we algebraically characterize communication links which are not used by an optimal flow. This leads to the characterization of minimal network structures supporting the maximal flows. We note that energy-balance, although implying global optimality, is a local property that can be computed efficiently and in a distributed manner. We suggest online distributed algorithms for energy-balance in different optimal network structures and numerically show their stability in particular setting. We remark that although the results obtained in this paper have a direct consequence in energy saving for wireless networks they do not limit themselves to this type of networks neither to energy as a resource. As a matter of fact, the results are much more general and can be used for any type of network and different types of resources.
[RACTI-RU1-2006-14] Aekaterinidis, Ioannis and Triantafillou, Peter, PastryStrings: A Comprehensive Content-Based Publish/Subscribe DHT Network, in: 26th IEEE International Conference on Distributed Computing and Systems (ICDCS 2006), 2006. [DOI]
In this work we propose and develop a comprehensive infrastructure, coined PastryStrings, for supporting rich queries on both numerical (with range, and comparison predicates) and string attributes, (accommodating equality, prefix, suffix, and containment predicates) over DHT networks utilising prefix-based routing. As event-based, publish/ subscribe information systems are a champion application class, we formulate our solution in terms of this environment.
[RACTI-RU1-2006-20] Aekaterinidis, Ioannis and Triantafillou, Peter, PastryStrings: Content-Based Publish/Subscribe over DHT Networks, 2006.
In this work we propose and develop a comprehensive infrastructure, coined PastryStrings, for supporting rich queries on both numerical (with range, and comparison predicates) and string attributes, (accommodating equality, prefix, suffix, and containment predicates) over DHT networks utilising prefix-based routing. As event-based, publish/subscribe information systems are a champion application class, we formulate our solution in terms of this environment.
[RACTI-RU1-2010-64] Kokkinos, Panagiotis, Manousakis, Kostas and Varvarigos, Emmanouel, Path Protection in WDM Networks with Quality of Transmission Limitations, in: International Conference on Communications, ICC 2010., 2010.
We consider path protection in the routing and wavelength assignment (RWA) problem for impairment constrained WDM optical networks. The proposed multicost RWA algorithms select the primary and the backup lightpaths by accounting for physical layer impairments. The backup lightpath may either be activated (1+1 protection) or it may be reserved and not activated, with activation taking place when/if needed (1:1 protection). In case of 1:1 protection the period of time where the quality of its transmission (QoT) is valid, despite the possible establishment of future connections, should be preserved, so as to be used in case the primary lightpath fails. We show that, by using the multicost approach for solving the RWA with protection problem, great benefits can be achieved both in terms of the connection blocking rate and in terms of the validity period of the backup lightpath. Moreover the multicost approach, by providing a set of candidate lightpaths for each source destination pair, instead of a single one, offers ease and flexibility in selecting the primary and the backup lightpaths.
Geographic routing scales well in sensor networks, mainly due to its stateless nature. Most of the algorithms in this area are concerned with guaranteeing a path toward the destination in the context of any network topology, while the optimality of the path is of little interest. In this paper, we are presenting a novel geographic routing algorithm with obstacle avoidance properties. It aims at finding the optimal path from a source to a destination when some areas of the network are unavailable for routing due to low local density or obstacle presence. It locally and gradually with time (but, as we show, quite fast) evaluates and updates the quality of the previously used paths and ignores non-optimal paths for further routing. By means of extensive simulations, we are comparing its performance to existing state of the art protocols, showing that it performs much better in terms of path length and hop count thus minimizing latency, overall traffic and energy consumption. Copyright � 2008 John Wiley & Sons, Ltd.
We demonstrate the use of impairment constraint routing for performance engineering of transparent metropolitan area optical networks. Our results show the relationship between blocking probability and different network characteristics such as span length, amplifier noise figure, and hit rate,and provide information on the system specifications required to achieve acceptable network performance.
[RACTI-RU1-2010-54] Kokkinos, Panagiotis, Azodolmolky, Siamak, Angelou, Marianna, Varvarigos, Emmanouel and Tomkos, Ioannis, Performance Evaluation of an Impairment-Aware Lightpath Computation Engine, in: 36th European Conference and Exhibition on Optical Communication, ECOC 2010, 2010.
We present a network operation tool called Impairment Aware Lightpath Computation Engine (IALCE) that incorporates an impairment-aware routing and wavelength assignment (RWA) algorithm. We perform experiments illustrating the flexibility of the engine and the performance of the algorithm
We present a detailed performance evaluation of a hybrid optical switching architecture called Overspill Routing in Optical Networks (ORION). The ORION architecture combines wavelength and (electronic) packet switching, so as to obtain the advantages of both switching paradigms. We have developed an extensive network simulator where the basic features of the ORION architecture were modeled, including suitable loadvarying sources and edge/core node architectures. Various aspects of the ORION architecture were studied including the routing policies used (i.e. once ORION always ORION and lightpath reentry) and the various options available for the buffer architecture. The complete network study shows that ORION can absorb temporary traffic overloads, as intended, provided sufficient buffering is present.
[RACTI-RU1-2004-28] Poster Proceedings of the 7th ACM MSWiM 2004, Ellinika Grammata and CTI Press, 2004.
This Volume contains the 11 papers corresponding to poster and demo presentations accepted to the 7th ACM/IEEE International Symposium on Modeling, Analysis and Simulation ofWireless and Mobile Systems (MSWiM 04), that is held October 4-6, 2004, in Venice, Italy. MSWiM 2004 (http://www.cs.unibo.it/mswim2004/) is intended to provide an international forum for original ideas, recent results and achievements on issues and challenges related to mobile and wireless systems. A Call for Posters was announced and widely disseminated, soliciting posters that report on recent original results or on-going research in the area of wireless and mobile networks. Prospective authors were encouraged to submit interesting results on all aspects of modeling, analysis and simulation of mobile and wireless networks and systems. The scope and topics of the Posters Session were the same as those included in the MSWiM Call for Papers (see above). Poster presentations were meant to provide authors with early feedback on their research work and enable them to present their research and exchange ideas during the Symposium. All submissions to the call for posters as well as selected papers submitted to MSWiM 04 were considered and reviewed. The review process resulted in accepting the set of 11 papers included in this Volume. Accepted posters will also be on display during the Symposium. The set of papers in this Proceedings covers a wide range of important topics in wireless and mobile computing, including channel allocation in wireless networks, quality of service provisioning in IEEE 802.11 wireless LANs, IP mobility support, energy conservation, routing in mobile adhoc networks, resource sharing, wireless access to the WWW, sensor networks etc. The performance evaluation techniques used include both analysis and simulation. We hope that the poster papers included in this Volume will facilitate a fruitful and lively discussion and exchange of interesting and creative ideas during the Symposium. We wish to thank the MSWiM Steering Committee Chair Azzedine Boukerche and the Program Co-Chairs ofMSWiM 04 Carla-Fabiana Chiasserini and Lorenzo Donatiello for their valuable help in the selection procedure. Also, the MSWiM 04 Publicity Co-Chairs Luciano Bononi, Helen Karatza and Mirela Sechi Moretti Annoni Notare for disseminating the Call for Posters. We wish to warmly thank the Poster Proceedings Chair Ioannis Chatzigiannakis for carefully doing an excellent job in preparing the Volume you now hold in your hands.
In this work we focus on the energy efficiency challenge in wireless sensor networks, from both an on-line perspective (related to routing), as well as a network design perspective (related to tracking). We investigate a few representative, important aspects of energy efficiency: a) the robust and fast data propagation b) the problem of balancing the energy dissipation among all sensors in the network and c) the problem of efficiently tracking moving entities in sensor networks. Our work here is a methodological survey of selected results that have alre dy appeared in the related literature. In particular, we investigate important issues of energy optimization, like minimizing the total energy dissipation, minimizing the number of transmissions as well as balancing the energy load to prolong the system�s lifetime. We review characteristic protocols and techniques in the recent literature, including probabilistic forwarding and local optimization methods. We study the problem of localizing and tracking multiple moving targets from a network design perspective i.e. towards estimating the least possible number of sensors, their positions and operation characteristics needed to efficiently perform the tracking task. To avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps. Under this model, we abstract the tracking network design problem by a covering combinatorial problem and then design and analyze an efficient approximate method for sensor placement and operation.
[RACTI-RU1-2006-71] Aekaterinidis, Ioannis and Triantafillou, Peter, Publish/Subscribe Information Delivery With Substring Predicates, 2006.
The content-based publish/subscribe (pub/sub)paradigm for system design is becoming increasingly popular, offering unique benefits for a large number of data-intensive applications. Coupled with the peer-to-peer technology, it can serve as a central building block for such applications deployed over a large-scale network infrastructure. A key problem toward the creation of large-scale contentbased pub/sub infrastructures relates to dealing efficiently with continuous queries (subscriptions) with rich predicates on string attributes; In particular, efficiently and accurately matching substring queries to incoming events is an open problem. In this work we study this problem. We provide and analyze novel algorithms for processing subscriptions with substring predicates and events in a variety of environments. We provide experimental data demonstrating the relative performance behavior of the proposed algorithms using as key metrics the network bandwidth requirements, number of messages, load balancing, as well as requirements for extra routing state (and related maintenance) and design flexibility.
[RACTI-RU1-2007-96] Kokkinos, Panagiotis, Christodoulopoulos, Konstantinos, Doulamis, N. and Varvarigos, Emmanouel, Quality of Service Scheduling of Computation and Communication Resources in Grid Networks, Nova Publishers, 2007.
Grids offer a transparent interface to geographically scattered computation, communication, storage and other resources. In this chapter we propose and evaluate QoS-aware and fair scheduling algorithms for Grid Networks, which are capable of optimally or near-optimally assigning tasks to resources, while taking into consideration the task characteristics and QoS requirements. We categorize Grid tasks according to whether or not they demand hard performance guarantees. Tasks with one or more hard requirements are referred to as Guaranteed Service (GS) tasks, while tasks with no hard requirements are referred to as Best Effort (BE) tasks. For GS tasks, we propose scheduling algorithms that provide deadline or computational power guarantees, or offer fair degradation in the QoS such tasks receive in case of congestion. Regarding BE tasks our objective is to allocate resources in a fair way, where fairness is interpreted in the max-min fair share sense. Though, we mainly address scheduling problems on computation resources, we also look at the joint scheduling of communication and computation resources and propose routing and scheduling algorithms aiming at co-allocating both resource type so as to satisfy their respective QoS requirements.
[RACTI-RU1-2012-12] Angelopoulos, Constantinos Marios, Nikoletseas, Sotiris, Patroumpa, Dimitra and Raptopoulos, Christoforos, Radiation-aware Data Propagation in Wireless Sensor Networks, in: MOBIWAC, pages 11-18, 10th ACM International Symposium on Mobility Management and Wireless Access (ACM MOBIWAC) 2012, Paphos, 2012.
This research further investigates the recently introduced (in [4]) paradigm of radiation awareness in ambient environments with abundant heterogeneous wireless networking from a distributed computing perspective. We call radiation at a point of a wireless network the total amount of electromagnetic quantity the point is exposed to; our de nition incorporates the e ect of topology as well as the time domain and environment aspects. Even if the impact of radiation to human health remains largely unexplored and controversial, we believe it is worth trying to understand and control, in a way that does not decrease much the quality of service o ered to users of the wireless network. In particular, we here focus on the fundamental problem of e cient data propagation in wireless sensor networks, try- ing to keep latency low while maintaining at low levels the radiation cumulated by wireless transmissions. We rst propose greedy and oblivious routing heuristics that are radiation aware. We then combine them with temporal back-o schemes that use local properties of the network (e.g. number of neighbours, distance from sink) in order to spread" radiation in a spatio-temporal way. Our proposed radiation aware routing heuristics succeed to keep radiation levels low, while not increasing latency.
[RACTI-RU1-2008-34] Kinalis, Athanasios, Nikoletseas, Sotiris and Patroumpa, Dimitra, Random Walk with Stopping Times in Wireless Sensor Networks, 2008.
The sensor devices are battery powered thus energy is the most precious resource of a wireless sensor network since periodically replacing the battery of the nodes in large scale deployments is infeasible. The collected data is disseminated to a static control point { data sink in the network, using node to node { multi-hop data propagation, [4, 6]. However, sensor devices consume signi cant amounts of energy in addition to increased implementation complexity since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away
We consider the problem of planning a mixed line rate (MLR) wavelength division multiplexing (WDM) transport optical network. In such networks, different modulation formats are usually employed to support transmission at different line rates. Previously proposed planning algorithms have used a transmission reach bound for each modulation format/line rate, mainly driven by single line rate systems. However, transmission experiments in MLR networks have shown that physical layer interference phenomena are more severe among transmissions that utilize different modulation formats. Thus, the transmission reach of a connection with a specific modulation format/line rate depends also on the other connections that co-propagate with it in the network. To plan a MLR WDM network, we present routing and wavelength assignment (RWA) algorithms that adapt the transmission reach of each connection according to the use of the modulation formats/line rates in the network. The proposed algorithms are able to plan the network so as to alleviate cross-rate interference effects, enabling the establishment of connections of acceptable quality over paths that would otherwise be prohibited.
[RACTI-RU1-2007-114] Aracil, Javier, Akar, Nail, Bjornstad, S., Casoni, M., Christodoulopoulos, Konstantinos, Careglio, Davide, Fdez-Palacios, J., Gauger, C., de Dios, Oscar Gonzalez, Karasan, Ezhan, Klinkowskif, Miroslaw, Morato, D., Nejabati, Reza, Overby, H., Rafaelli, Carla, Simeonidou, Dimitra, Stolc, N., Tosi-Beleffi, G. and Vlachos, Kyriakos, Research in Optical Burst Switching with in the E-Photon/ONe Network of Excellence, in: Elsevier: Journal of Optical Switching and Networks, volume 4, number 1, pages 1-19, 2007.
This paper presents a summary of Optical Burst Switching (OBS) research within the VI framework program e-Photon/ONe network of excellence. The paper includes network aspects such as routing techniques, resilience and contention resolution, together with burst switch architectures. On the other hand, we also discuss traffic analysis issues, Quality of Service (QoS) schemes, TCP/IP over OBS and physical layer aspects for OBS.
[RACTI-RU1-2006-64] Vlachos, Kyriakos, Research in optical burst switching within the e-Photon/ONe network of excellence $ The e-Photon/ONe Network of Excellence, in: Optical Switching and Networking, volume 4, pages 1-19, 2006.
A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time and known data transfer size. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start and end transmission at each link so as to minimize the reception time at the destination, or optimize some other performance criterion. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so called non-dominated candidate paths, from which the optimal path can be found. We then propose two mechanisms to appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial-time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network propagation delays and link-state update policies have on performance.
We propose QoS-aware scheduling algorithms for Grid Networks that are capable of optimally or near-optimally assigning computation and communication tasks to grid resources. The routing and scheduling algorithms to be presented take as input the resource utilization profiles and the task characteristics and QoS requirements, and co-allocate resources while accounting for the dependencies between communication and computation tasks. Keywords: communication and computation utilization profiles, multicost routing and scheduling, grid computing.
A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time and known data transfer size. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start and end transmission at each link so as to minimize the reception time at the destination, or optimize some other performance criterion. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated candidate paths, from which the optimal path can be found. We then propose two mechanisms to appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network propagation delays and link-state update policies have on performance.
A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start so as to minimize the reception time at the destination, or some other QoS requirement. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated candidate paths, from which the optimal path can be found. By appropriately pruning the set of candidate paths using path pseudo-domination relationships, we also find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial time algorithms have performance that it is very close to that of the optimal algorithm.
Orthogonal Frequency Division Multiplexing (OFDM) has been recently proposed as a modulation technique for optical networks, due to its good spectral efficiency and impairment tolerance. Optical OFDM is much more flexible compared to traditional WDM systems, enabling elastic bandwidth transmissions. We consider the planning problem of an OFDMbased optical network where we are given a traffic matrix that includes the requested transmission rates of the connections to be served. Connections are provisioned for their requested rate by elastically allocating spectrum using a variable number of OFDM subcarriers. We introduce the Routing and Spectrum Allocation (RSA) problem, as opposed to the typical Routing and Wavelength Assignment (RWA) problem of traditional WDM networks, and present various algorithms to solve the RSA. We start by presenting an optimal ILP RSA algorithm that minimizes the spectrum used to serve the traffic matrix, and also present a decomposition method that breaks RSA into two substituent subproblems, namely, (i) routing and (ii) spectrum allocation (R+SA) and solves them sequentially. We also propose a heuristic algorithm that serves connections one-by-one and use it to solve the planning problem by sequentially serving all traffic matrix connections. To feed the sequential algorithm, two ordering policies are proposed; a simulated annealing meta-heuristic is also proposed to obtain even better orderings. Our results indicate that the proposed sequential heuristic with appropriate ordering yields close to optimal solutions in low running times.
In this paper we demonstrate the significant impact of the user mobility rates on the performance on two different approaches for designing routing protocols for ad-hoc mobile networks: (a) the route creation and maintenance approach and (b) the "support" approach, that forces few hosts to move acting as "helpers" for message delivery. We study a set of representative protocols for each approach, i.e.~DSR and ZRP for the first approach and RUNNERS for the second. We have implemented the three protocols and performed a large scale and detailed simulation study of their performance. Our findings are: (i) DSR achieves low message delivery rates but manages to deliver messages very fast; (ii) ZRP behaves well in networks of low mobility rate, while its performance drops for networks of highly mobile users; (iii) RUNNERS seem to tolerate well (and in fact benefit from) high mobility rates. Based on our investigation, we design and implement two new protocols that result from the synthesis of the investigated routing approaches. We conducted an extensive, comparative simulation study of their performance. The new protocols behave well both in networks of diverse mobility motion rates, and in some cases they even outperform the original ones by achieving lower message delivery delays.
[RACTI-RU1-2004-66] Triantafillou, Peter, Self-Organization and Volunteering: Engineering in Very Large Scale Sharing Networks, in: International Workshop on Self-Properties in Complex Information Systems, 2004.
Our position is that a key to research efforts on ensuring high performance in very large scale sharing networks is the idea of volunteering; recognizing that such networks are comprised of largely heterogeneous nodes in terms of their capacity and behaviour, and that, in many real-world manifestations, a few nodes carry the bulk of the request service load. In this paper we outline how we employ volunteering as the basic idea using which we develop altruism-endowed self-organizing sharing networks to help solve two open problems in large-scale peer-topeer networks: (i) to develop an overlay topology structure that enjoys better performance than DHT-structured networks and, specifically, to offer O(log log N) routing performance in a network of N nodes, instead of O(log N), and (ii) to efficiently process complex queries and range queries, in particular.
Geographic routing is becoming the protocol of choice for many sensor network applications. The current state of the art is unsatisfactory: some algorithms are very efficient, however they require a preliminary planarization of the communication graph. Planarization induces overhead and is thus not realistic for some scenarios such as the case of highly dynamic network topologies. On the other hand, georouting algorithms which do not rely on planarization have fairly low success rates and fail to route messages around all but the simplest obstacles. To overcome these limitations, we propose the GRIC geographic routing algorithm. It has absolutely no topology maintenance overhead, almost 100% delivery rates (when no obstacles are added), bypasses large convex obstacles, finds short paths to the destination, resists link failure and is fairly simple to implement. The case of hard concave obstacles is also studied; such obstacles are hard instances for which performance diminishes.
[RACTI-RU1-2010-55] Christodoulopoulos, Konstantinos, Tomkos, Ioannis and Varvarigos, Emmanouel, Spectrally/Bitrate Flexible Optical Network Planning, in: 36th European Conference and Exhibition on Optical Communication, ECOC 2010, 2010.
We consider the Routing and Spectrum Allocation (RSA) problem in an OFDM-based optical network with elastic bandwidth allocation. We asses the spectrum utilization gains of this flexible architecture compared to a traditional fixed-grid rigid-bandwidth WDM network
[RACTI-RU1-2004-13] Dimitriou, Tassos, Krontiris, Ioannis, Nikakis, Fotios and Spirakis, Paul, SPEED: Scalable Protocols for Efficient Event Delivery in Sensor Networks, in: NETWORKING 2004, pages 1300-1305, 2004.
One of the most eminent problems in sensor networks is the routing of data to a central destination in a robust and e�cient manner. In this work we propose a new scalable protocol for propagating infor- mation about a sensed event towards a receiving center. Using only local information and total absence of coordination between sensors our pro- tocol achieves to propagate the sensed data to a receiving center by ac- tivating only those nodes that lie very close to the optimal path between the source of the event and the destination, resulting in low activation of the network's sensors. Thus the protocol is very energy e�cient. Further- more, our protocol is robust as it manages to propagate the information even when sensors fail with certain probability.
[RACTI-RU1-2006-89] Diaz, Josep, Koukopoulos, Dimitrios, Nikoletseas, Sotiris, Serna, Maria, Spirakis, Paul and Thilikos, D, Stability and non-stability of the FIFO protocol, in: ACM Symposium on Parallel Algorithms and Architectures, pages 48-52, 2006.
In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≰ 0.1428. We generalize this results to show upper bound for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≱ 0.8357, improving the previous known bounds of [2].
We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We provide substantial evidence for the Fully Mixed Nash Equilibrium Conjecture, which states that the worst Nash equilibrium is the fully mixed Nash equilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nash equilibrium is within a factor of 2h(1+ɛ) of that of the fully mixed Nash equilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic. Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is View the MathML source-hard to approximate the worst social cost within a multiplicative factor better than 2-2/(m+1).
We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.We provide substantial evidence for the Fully Mixed Nash Equilibrium Conjecture, which states that the worst Nash equilibrium is the fully mixed Nash equilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nash equilibrium is within a factor of 2h(1 + {\aa}) of that of the fully mixed Nash equilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic.Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is N P-hard to approximate the worst social cost within a multiplicative factor better than 2 - 2/(m + 1).
We investigate the impact of different mobility rates on the performance of routing protocols in ad-hoc mobile networks. Based on our investigation, we design a new protocol that results from the synthesis of the well known protocols: ZRP and RUNNERS. We have implemented the new protocol as well as the original two protocols and conducted an extensive, comparative simulation study of their performance. The new protocol behaves well both in networks of diverse mobility motion rates, and in some cases even outperforms the original ones by achieving lower message delivery delays.
[RACTI-RU1-2013-42] Kannan, Rajgopal, Busch, Costas and Spirakis, Paul, The Price of Anarchy is Unbounded for Congestion Games with Superpolynomial Latency Costs, in: CoRR, 2013.
We consider non-cooperative unsplittable congestion games where players share resources, and each player's strategy is pure and consists of a subset of the resources on which it applies a fixed weight. Such games represent unsplittable routing flow games and also job allocation games. The congestion of a resource is the sum of the weights of the players that use it and the player's cost function is the sum of the utilities of the resources on its strategy. The social cost is the total weighted sum of the player's costs. The quality of Nash equilibria is determined by the price of anarchy (PoA) which expresses how much worse is the social outcome in the worst equilibrium versus the optimal coordinated solution. In the literature the predominant work has only been on games with polynomial utility costs, where it has been proven that the price of anarchy is bounded by the degree of the polynomial. However, no results exist on general bounds for non-polynomial utility functions. Here, we consider general versions of these games in which the utility of each resource is an arbitrary non-decreasing function of the congestion. In particular, we consider a large family of superpolynomial utility functions which are asymptotically larger than any polynomial. We demonstrate that for every such function there exist games for which the price of anarchy is unbounded and increasing with the number of players (even if they have infinitesimal weights) while network resources remain fixed. We give tight lower and upper bounds which show this dependence on the number of players. Furthermore we provide an exact characterization of the PoA of all congestion games whose utility costs are bounded above by a polynomial function. Heretofore such results existed only for games with polynomial cost functions.
[RACTI-RU1-2009-8] Kaporis, Alexis and Spirakis, Paul, The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions, in: Symposium on Parallel Algorithms and Architectures (SPAA), pages 745-755, 2009.
Let M be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [E. Koutsoupias, C. Papadimitriou, Worst-case equilibria, in: 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS, vol. 1563, 1999, pp. 404-413; T. Roughgarden, E. Tardos, How bad is selfish routing? in: 41st IEEE Annual Symposium of Foundations of Computer Science, FOCS, 2000, pp. 93-102]. A Leader can decrease the coordination ratio by assigning flow {\'a}r on M, and then all Followers assign selfishly the (1-{\'a})r remaining flow. This is a Stackelberg Scheduling Instance(M,r,{\'a}),0≤{\'a}≤1. It was shown [T. Roughgarden, Stackelberg scheduling strategies, in: 33rd Annual Symposium on Theory of Computing, STOC, 2001, pp. 104-113] that it is weakly NP-hard to compute the optimal Leader's strategy. For any such network M we efficiently compute the minimum portion @b"M of flow r>0 needed by a Leader to induce M's optimum cost, as well as her optimal strategy. This shows that the optimal Leader's strategy on instances (M,r,@a>=@b"M) is in P. Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess's Paradox graph, such that no strategy controlling {\'a}r flow can induce ≤1/{\'a} times the optimum cost. However, we show that our main result also applies to any s-t net G. We take care of the Braess's graph explicitly, as a convincing example. Finally, we extend this result to k commodities. A conference version of this paper has appeared in [A. Kaporis, P. Spirakis, The price of optimum in stackelberg games on arbitrary single commodity networks and latency functions, in: 18th annual ACM symposium on Parallelism in Algorithms and Architectures, SPAA, 2006, pp. 19-28]. Some preliminary results have also appeared as technical report in [A.C. Kaporis, E. Politopoulou, P.G. Spirakis, The price of optimum in stackelberg games, in: Electronic Colloquium on Computational Complexity, ECCC, (056), 2005].
We study the problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links. We assume a collection of n network users; each user employs a mixed strategy, which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum (over all links) latency is minimized. We consider both uniform and arbitrary link capacities. How much decrease in global performace is necessary due to the absence of some central authority to regulate network traffic and implement an optimal assignment of traffic to links? We investigate this fundamental question in the context of Nash equilibria for such a system, where each network user selfishly routes its traffic only on those links available to it that minimize its expected latency cost, given the network congestion caused by the other users. We use the Coordination Ratio, originally defined by Koutsoupias and Papadimitriou, as a measure of the cost of lack of coordination among the users; roughly speaking, the Coordination Ratio is the ratio of the expectation of the maximum (over all links) latency in the worst possible Nash equilibrium, over the least possible maximum latency had global regulation been available. Our chief instrument is a set of combinatorial Minimum Expected Latency Cost Equations, one per user, that characterize the Nash equilibria of this system. These are linear equations in the minimum expected latency costs, involving the user traffics, the link capacities, and the routing pattern determined by the mixed strategies. In turn, we solve these equations in the case of fully mixed strategies, where each user assigns its traffic with a strictly positive probability to every link, to derive the first existence and uniqueness results for fully mixed Nash equilibria in this setting. Through a thorough analysis and characterization of fully mixed Nash equilibria, we obtain tight upper bounds of no worse than O(ln n/ln ln n) on the Coordination Ratio for (i) the case of uniform capacities and arbitrary traffics and (ii) the case of arbitrary capacities and identical traffics.
In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a Nash equilibrium, constructing a Nash equilibrium with given support characteristics, constructing the worst Nash equilibrium (the one with maximum social cost), constructing the best Nash equilibrium (the one with minimum social cost), or computing the social cost of a (given) Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results (both as NP-hardness and #P-completeness results), and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system.
The peer-to-peer computing paradigm is an intriguing alternative to Google-style search engines for querying and ranking Web content. In a network with many thousands or millions of peers the storage and access load requirements per peer are much lighter than for a centralized Google-like server farm; thus more powerful techniques from information retrieval, statistical learning, computational linguistics, and ontological reasoning can be employed on each peer�s local search engine for boosting the quality of search results. In addition, peers can dynamically collaborate on advanced and particularly difficult queries. Moroever, a peer-to-peer setting is ideally suited to capture local user behavior, like query logs and click streams, and disseminate and aggregate this information in the network, at the discretion of the corresponding user, in order to incorporate richer cognitive models. This paper gives an overview of ongoing work in the EU Integrated Project DELIS that aims to develop foundations for a peer-to-peer search engine with Google-or-better scale, functionality, and quality, which will operate in a completely decentralized and self-organizing manner. The paper presents the architecture of such a system and the Minerva prototype testbed, and it discusses various core pieces of the approach: efficient execution of top-k ranking queries, strategies for query routing when a search request needs to be forwarded to other peers, maintaining a self-organizing semantic overlay network, and exploiting and coping with user and community behavior.
[RACTI-RU1-2003-43] Vlachos, Kyriakos, Pleros, N., Bintjas, C, Theophilopoulos, G and Avramopoulos, Hercules, Ultrafast time domain technology and its application in all-optical signal processing, in: Lightwave Technology, volume 21, number 9, pages 1857-1868, ISSN 0733-8724, 2003. [DOI]
In this paper, we review recent advances in ultrafast optical time-domain technology with emphasis on the use in optical packet switching. In this respect, several key building blocks, including high-rate laser sources applicable to any time-division-multiplexing (TDM) application, optical logic circuits for bitwise processing, and clock-recovery circuits for timing synchronization with both synchronous and asynchronous data traffic, are described in detail. The circuits take advantage of the ultrafast nonlinear transfer function of semiconductor-based devices to operate successfully at rates beyond 10 Gb/s. We also demonstrate two more complex circuits-a header extraction unit and an exchange-bypass switch-operating at 10 Gb/s. These two units are key blocks for any general-purpose packet routing/switching application. Finally, we discuss the system perspective of all these modules and propose their possible incorporation in a packet switch architecture to provide low-level but high-speed functionalities. The goal is to perform as many operations as possible in the optical domain to increase node throughput and to alleviate the network from unwanted and expensive optical-electrical-optical conversions.
[RACTI-RU1-2011-92] Manousakis, Kostas and Varvarigos, Emmanouel, Using a Nature Inspired Technique to Train a Dynamic IA-RWA Algorithm, in: 18th International Conference on Telecommunications, pages 61-66, ICT, 2011.
In this work we add a training phase to an Impairment Aware Routing and Wavelength Assignment (IA-RWA) algorithm so as to improve its performance. The initial IA-RWA algorithm is a multi-parametric algorithm where a vector of physical impairment parameters is assigned to each link, from which the impairment vectors of candidate lightpaths are calculated. The important issue here is how to combine these impairment parameters into a scalar that would reflect the true transmission quality of a path. The training phase of the proposed IA-RWA algorithm is based on an optimization approach, called Particle Swarm Optimization (PSO), inspired by animal social behavior. The training phase gives the ability to the algorithm to be aware of the physical impairments even though the optical layer is seen as a black box. Our simulation studies show that the performance of the proposed scheme is close to that of algorithms that have explicit knowledge of the optical layer and the physical impairments.
[RACTI-RU1-2007-90] Caragiannis, Ioannis, Wavelength management in WDM rings to maximize the number of connections, in: 24th International Symposium on Theoretical Aspects of Computer Science (STACS 2007), pages 61-72, Springer Berlin / Heidelberg, 2007. [DOI]
We study computationally hard combinatorial problems arising from the important engineering question of how to maximize the number of connections that can be simultaneously served in a WDM optical network. In such networks, WDM technology can satisfy a set of connections by computing a route and assigning a wavelength to each connection so that no two connections routed through the same fiber are assigned the same wavelength. Each fiber supports a limited number of w wavelengths and in order to fully exploit the parallelism provided by the technology, one should select a set connections of maximum cardinality which can be satisfied using the available wavelengths. This is known as the maximum routing and path coloring problem (maxRPC). Our main contribution is a general analysis method for a class of iterative algorithms for a more general coloring problem. A lower bound on the benefit of such an algorithm in terms of the optimal benefit and the number of available wavelengths is given by a benefit-revealing linear program. We apply this method to maxRPC in both undirected and bidirected rings to obtain bounds on the approximability of several algorithms. Our results also apply to the problem maxPC where paths instead of connections are given as part of the input. We also study the profit version of maxPC in rings where each path has a profit and the objective is to satisfy a set of paths of maximum total profit.
[RACTI-RU1-2003-13] Lucking, Thomas, Mavronicolas, Marios, Monien, Burkhart, Rode, Manuel, Spirakis, Paul and Vrto, Imrich, Which Is the Worst-Case Nash Equilibrium?, in: Mathematical Foundations of Computer Science, pages 551-561, Springer Berlin / Heidelberg, 2003. [DOI]
A Nash equilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such equilibria within the context of a certain game that models selfish routing for a set of n users each shipping its traffic over a network consisting of m parallel links. In particular, we are interested in identifying the worst-case Nash equilibrium – the one that maximizes social cost. Worst-case Nash equilibria were first introduced and studied in the pioneering work of Koutsoupias and Papadimitriou [9]. More specifically, we continue the study of the Conjecture of the Fully Mixed Nash Equilibrium, henceforth abbreviated as FMNE Conjecture, which asserts that the fully mixed Nash equilibrium, when existing, is the worst-case Nash equilibrium. (In the fully mixed Nash equilibrium, the mixed strategy of each user assigns (strictly) positive probability to every link.) We report substantial progress towards identifying the validity, methodologies to establish, and limitations of, the FMNE Conjecture.
[RACTI-RU1-2010-4] Baumgartner, Tobias, Chatzigiannakis, Ioannis, Fekete, Sandor, Koninis, Christos, Kr�ller, Alexander and Pyrgelis, Apostolos, Wiselib: A Generic Algorithm Library for Heterogeneous Sensor Networks, in: 7th European Conference on Wireless Sensor Networks (EWSN 2010), pages 162-177, Springer Berlin / Heidelberg, Coimbra, Portugal, 2010. [DOI]
There exists a great amount of algorithms for wireless sensor networks (WSNs) that have never been tried in practice. This is due to the fact that programming sensor nodes still happens on a very technical level. We remedy the situation by introducing our algorithm library Wiselib, which allows for simple implementations of algorithms. It can adopt to a large variety of hardware and software. This is achieved by employing advanced C++ techniques such as templates and inline functions, which allow to write generic code that is resolved and bound at compile time, resulting in virtually no memory or computation overhead at run time. The Wiselib runs on different host operating systems such as Contiki, iSense OS, and ScatterWeb. Furthermore, it runs on virtual nodes simulated by Shawn. The Wiselib provides an algorithm with data structures that suit the specific properties of the target platform. Algorithm code does not contain any platform-specific specializations, allowing a single implementation to run natively on heterogeneous networks. In this paper, we describe the building blocks of the Wiselib, analyze the overhead, and show how cryptographically secured routing algorithms can be implemented. We also report on results from experiments with real sensor node hardware.