More Like this

1. Fast IP Hopping Randomization to Secure Hop-by-Hop Access in SDN

   https://doi.org/10.1109/TNSM.2018.2889842  

   Chang, Sang-Yoon; Park, Younghee; Ashok Babu, Bhavana Babu (March 2019, IEEE Transactions on Network and Service Management)
2. Hop-constrained oblivious routing

   https://doi.org/10.1145/3406325.3451098  

   Ghaffari, Mohsen; Haeupler, Bernhard; Zuzic, Goran (June 2021, Symposium on Theory of Computing (STOC))

   null (Ed.)

   We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing. Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize (congestion + dilation), defined as follows: The dilation is the maximum path hop-length, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have (congestion + dilation) within a poly(logn) factor of the best possible value. More precisely, for any integer hop-bound h, this oblivious routing scheme selects paths of length at most h · poly(logn) and is poly(logn)-competitive in terms of congestion in comparison to the best possible congestion achievable via paths of length at most h hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of R'acke [FOCS 2002, STOC 2008], which are O(logn)-competitive in terms of congestion, but are not competitive in terms of dilation. 

   more » « less
3. One Hop Greedy Permutations

   Sheehy, Donald R. (January 2020, Proceedings of the 32nd Canadian Conference on Computational Geometry)

   Keil, Mark; Mondal, Debajyoti (Ed.)

   We adapt and generalize a heuristic for k-center clustering to the permutation case, where every pre x of the ordering is a guaranteed approximate solution. The one-hop greedy permutations work by choosing at each step the farthest unchosen point and then looking in its local neighborhood for a point that covers the most points at a certain scale. This balances the competing demands of reducing the coverage radius and also covering as many points as possible. This idea first appeared in the work of Garcia-Diaz et al. and their algorithm required O(n2 log n) time for a fi xed k (i.e. not the whole permutation). We show how to use geometric data structures to approximate the entire permutation in O(n log D
   ) time for metrics sets with spread D. Notably, this running time is asymptotically the same as the running time for computing the ordinary greedy permutation. 

   more » « less
4. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing

   https://doi.org/10.4230/LIPIcs.ESA.2024.41  

   Chekuri, Chandra; Jain, Rhea (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hop-constrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail. 

   more » « less
5. Hop spanners for geometric intersection graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2022.30  

   Conroy, Jonathan B.; Toth, Csaba D. (June 2022, 38th International Symposium on Computational Geometry)