Survivability in time-varying networks
Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109182 https://orcid.org/0000-0003-3055-906X https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826217159464845312 |
|---|---|
| author | Liang, Qingkai Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Liang, Qingkai Modiano, Eytan H |
| author_sort | Liang, Qingkai |
| collection | MIT |
| description | Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then we analyze the complexity of computing the proposed metrics and develop approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework in the robust design of a real-world bus communication network. |
| first_indexed | 2024-09-23T16:58:58Z |
| format | Article |
| id | mit-1721.1/109182 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:58:58Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1091822022-09-29T22:51:05Z Survivability in time-varying networks Liang, Qingkai Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Liang, Qingkai Modiano, Eytan H Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then we analyze the complexity of computing the proposed metrics and develop approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework in the robust design of a real-world bus communication network. 2017-05-18T20:17:24Z 2017-05-18T20:17:24Z 2016-07 2016-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-9953-1 http://hdl.handle.net/1721.1/109182 Liang, Qingkai and Modiano, Eytan. “Survivability in Time-Varying Networks.” IEEE INFOCOM 2016,The 35th Annual IEEE International Conference on Computer Communications, April 10-14 2016, San Francisco, California, Institute of Electrical and Electronics Engineers (IEEE), July 2016 https://orcid.org/0000-0003-3055-906X https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/INFOCOM.2016.7524490 IEEE INFOCOM 2016 -IEEE INFOCOM 2016, The 35th Annual IEEE International Conference on Computer Communications Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Liang, Qingkai Modiano, Eytan H Survivability in time-varying networks |
| title | Survivability in time-varying networks |
| title_full | Survivability in time-varying networks |
| title_fullStr | Survivability in time-varying networks |
| title_full_unstemmed | Survivability in time-varying networks |
| title_short | Survivability in time-varying networks |
| title_sort | survivability in time varying networks |
| url | http://hdl.handle.net/1721.1/109182 https://orcid.org/0000-0003-3055-906X https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT liangqingkai survivabilityintimevaryingnetworks AT modianoeytanh survivabilityintimevaryingnetworks |