Publications

• Christina Vlachou, Albert Banchs, Julien Herzen and Patrick Thiran. Analyzing and Boosting the Performance of Power-Line Communication Networks. in ACM CoNEXT, 2014.
  PDF BibTeX Abstract Description of experimental framework and simulator (PDF)

  @InProceedings{vlachou2014analyzing}
     author      = {Vlachou, Christina and Banchs, Albert and Herzen, Julien
                   and Thiran, Patrick},
     booktitle   = {{ACM} {C}o{NEXT}},
     location    = {Sydney, Australia},
     title       = {{A}nalyzing and {B}oosting the {P}erformance of {P}ower-{L}ine {C}ommunication {N}etworks},
     year        = 2014
  }
                  

  Power-line communications are employed in home networking to provide easy and high-throughput connectivity. IEEE 1901, the MAC protocol for power-line networks, employs a CSMA/CA protocol similar to that of 802.11, but is substantially more complex, which probably explains why little is known about its performance. One of the key differences between the two protocols is that whereas 802.11 only reacts upon collisions, 1901 also reacts upon several consecutive transmissions and thus can potentially achieve better performance by avoiding unnecessary collisions. In this paper, we propose a model for the 1901 MAC. Our analysis reveals that the default configuration of 1901 does not fully exploit its potential and that its performance degrades with the number of stations. We derive analytically the optimal configuration parameters for 1901; this drastically improves throughput and achieves optimal performance without requiring the knowledge of the number of stations in the network. In contrast, to provide a similar performance, 802.11 requires knowing the number of contending stations, which is unfeasible for realistic traffic patterns. Our solution can be readily implemented by vendors, as it only consists in modifying existing MAC parameters. We corroborate our results with testbed measurements, unveiling a significant signaling overhead in 1901 implementations.

• Christina Vlachou, Albert Banchs, Julien Herzen and Patrick Thiran. On the MAC for Power-Line Communications: Modeling Assumptions and Performance Tradeoffs. in IEEE ICNP, 2014.
  (Best paper runner-up award)
  PDF BibTeX Abstract Technical report with proof extensions (PDF) Description of experimental framework and simulator (PDF)

  @InProceedings{vlachou2014plcmac,
     author      = {Vlachou, Christina and Banchs, Albert and Herzen, Julien
                   and Thiran, Patrick},
     booktitle   = {{IEEE} {I}nternational {C}onference on {N}etwork {P}rotocols ({ICNP})},
     location    = {The Research Triangle, North Carolina},
     title       = {On the {MAC} for {P}ower-{L}ine {C}ommunications:
                   {M}odeling {A}ssumptions and {P}erformance {T}radeoffs},
     year        = 2014
  }
                  

  Power-line communications are becoming a key component in home networking. The dominant MAC protocol for high data-rate power-line communications, IEEE 1901, employs a CSMA/CA mechanism similar to the backoff process of 802.11. Existing performance evaluation studies of this protocol assume that the backoff processes of the stations are independent (the so-called decoupling assumption). However, in contrast to 802.11, 1901 stations can change their state after sensing the medium busy, which introduces strong coupling between the stations, and, as a result, makes existing analyses inaccurate. In this paper, we propose a new performance model for 1901, which does not rely on the decoupling assumption. We prove that our model admits a unique solution. We confirm the accuracy of our model using both testbed experiments and simulations, and we show that it surpasses current models based on the decoupling assumption. Furthermore, we study the tradeoff between delay and throughput existing with 1901. We show that this protocol can be configured to accommodate different throughput and jitter requirements, and give systematic guidelines for its configuration.

• Vincent Etter, Julien Herzen (co-first author), Matthias Grossglauser and Patrick Thiran. Mining Democracy. ACM COSN, 2014.
  (Best paper award)
  PDF BibTeX Abstract Slides Predikon

  @inproceedings{etter2014cosn,
      author = "Etter, Vincent and Herzen, Julien and Grossglauser, Matthias and Thiran, Patrick",
      title = "Mining Democracy",
      booktitle = "Proceedings of the second ACM Conference on Online Social Networks",
      series = "COSN '14",
      year = "2014",
  }
  

  Switzerland has a long tradition of direct democracy, which makes it an ideal laboratory for research on real-world politics. Similar to recent open government initiatives launched worldwide, the Swiss government regularly releases datasets related to state affairs and politics. In this paper, we propose an exploratory, data-driven study of the political landscape of Switzerland, in which we use opinions expressed by candidates and citizens on a web platform during the recent Swiss parliamentary elections, together with fine-grained vote results and parliament votes.

  Following this purely data-driven approach, we show that it is possible to uncover interesting patterns that would otherwise require both tedious manual analysis and domain knowledge. In particular, we show that traditional cultural and/or ideological idiosyncrasies can be highlighted and quantified by looking at vote results and pre-election opinions. We propose a technique for comparing the candidates' opinions expressed before the elections with their actual votes cast in the parliament after the elections. This technique spots politicians that do not vote consistently with the opinions that they expressed during the campaign. We also observe that it is possible to predict surprisingly precisely the outcome of nationwide votes, by looking at the outcome in a single, carefully selected municipality. Our work applies to any country where similar data is available; it points to some of the avenues created by user-generated data emerging from open government initiatives, which enable new data-mining approaches to political and social sciences.

• Christina Vlachou, Albert Banchs, Julien Herzen and Patrick Thiran. Performance Analysis of MAC for Power-Line Communications. ACM Sigmetrics (poster session), 2014.
  PDF Poster BibTeX Abstract

  @InProceedings{vlachou2014performance,
     affiliation = {EPFL},
     author      = {Vlachou, Christina and Banchs, Albert and Herzen, Julien
                   and Thiran, Patrick},
     booktitle   = {{ACM} {SIGMETRICS} 2014 (poster session)},
     details     = {http://infoscience.epfl.ch/record/197975},
     documenturl = {http://infoscience.epfl.ch/record/197975/files/sig0256-vlachou.pdf},
     doi         = {10.1145/2591971.2592033},
     keywords    = {Power-line communications; CSMA/CA; analysis},
     location    = {Austin, Texas, USA},
     title       = {Performance {A}nalysis of {MAC} for {P}ower-{L}ine {C}ommunications},
     year        = 2014
  }
                      

  We investigate the IEEE 1901 MAC protocol, the dominant protocol for high data rate power-line communications. 1901 employs a CSMA/CA mechanism similar to – but much more complex than – the backoff mechanism of 802.11. Because of this extra complexity, and although this mechanism is the only widely used MAC layer for power-line networks, there are few analytical results on its performance. We propose a model for the 1901 MAC that comes in the form of a single fixed-point equation for the collision probability. We prove that this equation admits a unique solution, and we evaluate the accuracy of our model by using simulations.

• Julien Herzen, Ruben Merz and Patrick Thiran. SAW: Spectrum Assignment for WLANs. ACM S3, 2013.
  PDF BibTeX Abstract

                      @InProceedings{herzen2013saw,
                         affiliation = {EPFL},
                         author      = {Herzen, Julien and Merz, Ruben and Thiran, Patrick},
                         booktitle   = {{ACM} {S}3 2013},
                         details     = {http://infoscience.epfl.ch/record/189777},
                         documenturl = {http://infoscience.epfl.ch/record/189777/files/saw-s3_1.pdf},
                         location    = {Miami, Florida, USA},
                         oai-id      = {oai:infoscience.epfl.ch:189777},
                         title       = {{SAW}: {S}pectrum {A}ssignment for {WLAN}s},
                         year        = 2013
                      }
                      

  We consider the problem of jointly allocating channel center-frequencies and bandwidths for IEEE 802.11 wireless LANs (WLANs). The bandwidth used on a link significantly affects both the capacity experienced on this link and the interference produced on neighboring links. Therefore, when jointly assigning both center frequencies and channel widths, a trade-off must be found between interference mitigation and the potential capacity offered on each link. We study this trade-off and present SAW (spectrum assignment for WLANs), a decentralized algorithm that finds efficient configurations. SAW is tailored for 802.11 home networks. It is distributed, online and transparent. It does not require a central coordinator and it constantly adapts the spectrum usage without disrupting network traffic. The algorithm is decentralized and self-organizing; it provably converges towards efficient spectrum allocations. We evaluate SAW using both simulation and a deployment on an indoor testbed composed of off-the-shelf 802.11 hardware. We observe that it dramatically increases the overall network efficiency and fairness, even when some Access Points (APs) do not behave socially.

• Julien Herzen, Ruben Merz and Patrick Thiran. Distributed Spectrum Assignment for Home WLANs. IEEE Infocom, 2013.
  PDF Slides Poster BibTeX Abstract Technical report with additional proofs and results (PDF)

  @INPROCEEDINGS{herzen2013distributed,
  author={Herzen, J. and Merz, R. and Thiran, P.},
  booktitle={INFOCOM, 2013 Proceedings IEEE},
  title={Distributed spectrum assignment for home WLANs},
  year={2013},
  month={April},
  pages={1573-1581},
  keywords={home networks;radio links;radio spectrum management;radiofrequency interference;radiofrequency measurement;wireless LAN;wireless channels;AP;IEEE 802.11 home networks;IEEE 802.11 wireless LAN;SAW;access points;channel center frequencies allocation;channel widths;distributed spectrum assignment;home WLAN;indoor testbed;interference mitigation;network efficiency;network traffic;off-the-shelf 802.11 hardware;out-of-band measurements;spectrum allocation decisions;Bandwidth;IEEE 802.11 Standards;Interference;Monitoring;Radio spectrum management;Resource management;Surface acoustic waves},
  doi={10.1109/INFCOM.2013.6566953},
  ISSN={0743-166X},}
                      

  We consider the problem of jointly allocating channel center frequencies and bandwidths for IEEE 802.11 wireless LANs (WLANs). The bandwidth used on a link affects significantly both the capacity experienced on this link and the interference produced on neighboring links. Therefore, when jointly assigning both center frequencies and channel widths, there is a trade-off between interference mitigation and the potential capacity offered on each link. We study this tradeoff and we present SAW (spectrum assignment for WLANs), a decentralized algorithm that finds efficient configurations. SAW is tailored for 802.11 home networks. It is distributed, online and transparent. It does not require a central coordinator and it constantly adapts the spectrum usage without disrupting network traffic. A key feature of SAW is that the access points (APs) need only a few out-of-band measurements in order to make spectrum allocation decisions. Despite being completely decentralized, the algorithm is self-organizing and provably converges towards efficient spectrum allocations. We evaluate SAW using both simulation and a deployment on an indoor testbed composed of off-the-shelf 802.11 hardware. We observe that it dramatically increases the overall network efficiency and fairness.

• Christina Vlachou, Julien Herzen and Patrick Thiran. Fairness of MAC protocols: IEEE 1901 vs. 802.11. IEEE ISPLC, 2013.
  PDF BibTeX Abstract

  @INPROCEEDINGS{vlachou2013fairness,
  author={Vlachou, C. and Herzen, J. and Thiran, P.},
  booktitle={Power Line Communications and Its Applications (ISPLC), 2013 17th IEEE International Symposium on},
  title={Fairness of MAC protocols: IEEE 1901 vs. 802.11},
  year={2013},
  month={March},
  pages={58-63},
  keywords={carrier sense multiple access;carrier transmission on power lines;wireless LAN;CSMA-CA method;IEEE 1901;IEEE 802.11;Jain fairness index;MAC protocol;packet delay;packet level:;power line communication;short-term fairness;wireless communication;CSMA/CA;HomePlug;Jain's fairness index;Medium Access Control (MAC);fairness;inter-transmissions},
  doi={10.1109/ISPLC.2013.6525825},}
  
                      

  The MAC layer of the IEEE 1901 standard for power line communications employs a CSMA/CA method similar to, but more complex than, this of IEEE 802.11 for wireless communications. The differences between these protocols raise questions such as which one performs better and under what conditions. We study the fairness of the 1901 MAC protocol in single contention domain networks, where all stations hear each other. We examine fairness at the packet level: a MAC layer protocol is fair if all stations share equitably the medium during a fixed time interval. We focus on short-term fairness, that is, over short time intervals. Short-term fairness directly impacts end-user experience, because unfair protocols are susceptible to introduce substantial packet delays. We evaluate short-term fairness with two metrics: Jain's fairness index and the number of inter-transmissions. We present test-bed results of both protocols and compare them with simulations. Both simulation and test-bed results indicate that 802.11 is fairer in the short-term when the number of stations N is between 2 and 5. However, simulation results reveal that 1901 is fairer in the short-term for N >= 15. Importantly, our test-bed measurements indicate that 1901 unfairness can cause significant additional delay when N = 2. Finally, we confirm these results by showing analytically that 1901 is short-term unfair for N = 2.

• Julien Herzen, Cedric Westphal and Patrick Thiran. Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol. IEEE ICNP, 2011.
  PDF Slides BibTeX Abstract Technical report with additional results (PDF)

  @INPROCEEDINGS{herzen2011scalable,
  author={Herzen, J. and Westphal, C. and Thiran, P.},
  booktitle={Network Protocols (ICNP), 2011 19th IEEE International Conference on},
  title={Scalable routing easy as PIE: A practical isometric embedding protocol},
  year={2011},
  month={Oct},
  pages={49-58},
  keywords={Internet;graph theory;greedy algorithms;packet radio networks;routing protocols;Internet;PIE;graph theory;greedy routing;memory polylogarithmic;packet routing;practical isometric embedding;scalable routing protocol;shortest path;Context;Internet;Measurement;Protocols;Routing;Scalability;Topology},
  doi={10.1109/ICNP.2011.6089081},}
                      

  We present PIE, a scalable routing scheme that achieves 100% packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a space of concise dimensionality, which enables greedy routing based only on local knowledge. PIE is a general routing scheme, meaning that it works on any graph. We focus however on the Internet, where routing scalability is an urgent concern. We show analytically and by using simulation that the scheme scales extremely well on Internet-like graphs. In addition, its geometric nature allows it to react efficiently to topological changes or failures by finding new paths in the network at no cost, yielding better delivery ratios than standard algorithms. The proposed routing scheme needs an amount of memory polylogarithmic in the size of the network and requires only local communication between the nodes. Although each node constructs its coordinates and routes packets locally, the path stretch remains extremely low, even lower than for centralized or less scalable state-of-the-art algorithms: PIE always finds short paths and often enough finds the shortest paths.

• Adel Aziz, Julien Herzen, Ruben Merz, Seva Shneer and Patrick Thiran. Enhance & Explore: an Adaptive Algorithm to Maximize the Utility of Wireless Networks. ACM MobiCom, 2011.
  PDF BibTeX Abstract

  @inproceedings{Aziz2011enhance,
   author = {Aziz, Adel and Herzen, Julien and Merz, Ruben and Shneer, Seva and Thiran, Patrick},
   title = {Enhance \&\#38; Explore: An Adaptive Algorithm to Maximize the Utility of Wireless Networks},
   booktitle = {Proceedings of the 17th Annual International Conference on Mobile Computing and Networking},
   series = {MobiCom '11},
   year = {2011},
   isbn = {978-1-4503-0492-4},
   location = {Las Vegas, Nevada, USA},
   pages = {157--168},
   numpages = {12},
   url = {http://doi.acm.org/10.1145/2030613.2030632},
   doi = {10.1145/2030613.2030632},
   acmid = {2030632},
   publisher = {ACM},
   address = {New York, NY, USA},
   keywords = {E\&\#38;E, WLAN, adaptive algorithm, congestion control, convergence proof, experimental evaluation, fairness, multi-hop networks, utility maximization, wireless networks},
  }
                      

  The goal of jointly providing efficiency and fairness in wireless networks can be seen as the problem of maximizing a given utility function. In contrast with wired networks, the capacity of wireless networks is typically time-varying and not known explicitly. Hence, as the capacity region is impossible to know or measure exactly, existing scheduling schemes either under-estimate it and are too conservative, or they over-estimate it and suffer from congestion collapse. We propose a new adaptive algorithm, called Enhance & Explore (E&E). It maximizes the utility of the network without requiring any explicit characterization of the capacity region. E&E works above the MAC layer and it does not demand any modification to the existing networking stack. We first evaluate our algorithm theoretically and we prove that it converges to a state of optimal utility. We then evaluate the performance of the algorithm in a WLAN setting, using both simulations and real measurements on a testbed composed of IEEE 802.11 wireless routers. Finally, we investigate a wireless mesh network setting and we find that, when coupled with an efficient mechanism for congestion control, the E&E algorithm greatly increases the utility achieved by multi-hop networks as well.

• Julien Herzen, Adel Aziz, Ruben Merz, Seva Shneer and Patrick Thiran. A Measurement-Based Algorithm to Maximize the Utility of Wireless Networks. ACM S3, 2011.
  PDF Slides BibTeX Abstract

  @inproceedings{herzen2011measurement,
   author = {Herzen, Julien and Aziz, Adel and Merz, Ruben and Shneer, Seva and Thiran, Patrick},
   title = {A Measurement-based Algorithm to Maximize the Utility of Wireless Networks},
   booktitle = {Proceedings of the 3rd ACM Workshop on Wireless of the Students, by the Students, for the Students},
   series = {S3 '11},
   year = {2011},
   isbn = {978-1-4503-0868-7},
   location = {Las Vegas, Nevada, USA},
   pages = {13--16},
   numpages = {4},
   url = {http://doi.acm.org/10.1145/2030686.2030691},
   doi = {10.1145/2030686.2030691},
   acmid = {2030691},
   publisher = {ACM},
   address = {New York, NY, USA},
   keywords = {capacity region, fairness, optimal, performance, rate region, simulation, testbed, utility function, wireless},
  } 
  
                      

  The goal of jointly providing fairness and efficiency in wireless networks can be seen as the problem of maximizing a given utility function. The main difficulty when solving this problem is that the capacity region of wireless networks is typically unknown and time-varying, which prevents the usage of traditional optimization tools. As a result, scheduling and congestion control algorithms are either too conservative because they under-estimate the capacity region, or suffer from congestion collapse because they over-estimate it. We propose a new adaptive congestion control algorithm, called Enhance & Explore (E&E). It maximizes the utility of the network without requiring any explicit characterization of the capacity region. E&E works above the MAC layer and is decoupled from the underlying scheduling mechanism. It provably converges to a state of optimal utility. We evaluate the performance of the algorithm in a WLAN setting, using both simulations and measurements on a real testbed composed of IEEE 802.11 wireless routers.

• Julien Herzen, Adel Aziz and Patrick Thiran. Demo Abstract of Net-Controller: a Network Visualization and Management Tool. IEEE Infocom (demo session), 2010.
  PDF BibTeX Abstract

  @InProceedings{herzen2010net,
     affiliation = {EPFL},
     author      = {Herzen, Julien and Aziz, Adel and Thiran, Patrick},
     booktitle   = {Infocom demo},
     details     = {http://infoscience.epfl.ch/record/146810},
     documenturl = {http://infoscience.epfl.ch/record/146810/files/INFOCOM10_HAT_final_v1.pdf},
     issn        = {0368-4466},
     keywords    = {NCCR-MICS; NCCR-MICS/ESDM},
     location    = {San Diego},
     oai-id      = {oai:infoscience.epfl.ch:146810},
     oai-set     = {conf},
     review      = {REVIEWED},
     status      = {PUBLISHED},
     title       = {Demo {A}bstract of {N}et-{C}ontroller: a {N}etwork
                   {V}isualization and {M}anagement {T}ool},
     year        = 2010
  }
                      

  Net-Controller is a user-friendly network visualization and management tool developed at EPFL in order to easily retrieve and display in real time network statistics, such as link throughput and queue occupancy from a large testbed composed of wireless routers. Additionally, Net-Controller allows to control and modify the parameters of a complete network from a central point, and to easily generate traffic between different nodes. We intend to illustrate some of the features of Net-Controller through two examples that show how easily this tool detects and helps elucidate the throughput degradation that occurs in a wireless multi-hop network. The first example shows how and why fair queuing [6] improves performance compared to the standard FIFO policy used in off-the-shelf routers. The second example shows how and why a hop-by-hop congestion control mechanism, such as EZ-Flow [4] is needed to tackle the instability problem of a multi-hop scenario.

Contact Information