@@ @

Publications

Journal Papers And Recent Conference Papers (from 2012)
	Efficient Service Chain Verification Using Sketches and Small Samples Reuven Cohen, Liran Katzir and Aviv Yehezkel Published In: IEEE NFV-SDN 2021 bibtex Abstract: A service function chain defines an ordered or partially ordered set of abstract service functions and ordering constraints that must be applied to packet flows as a result of classification. Service chain verification is an important logic, which should verify that each flow indeed traverses the intended set of services, and in the desired order. In this paper we address this service chain verification problem in a new way. The main idea is to convert each service chain verification instance to its ¿equivalent set-expression cardinality equation,¿ and to use statistical algorithms to verify that each equation is satisfied.
	Hardware SYN Attack Protection For High Performance Load Balancers Reuven Cohen, Matty Kadosh, Alan Lo and Qasem Sayah Published In: IEEE Hot Interconnects 2021 bibtex Abstract: SYN flooding is a simple and effective denial-of-service attack, in which an attacker sends many SYN requests to a target¿s server in an attempt to consume server resources and make it unresponsive to legitimate traffic. While SYN attacks have traditionally targeted web servers, they are also known to be very harmful to intermediate cloud devices, and in particular to stateful load balancers (LBs). Fighting against a SYN attack without negatively affecting legitimate connections is not easy, especially if the LB needs to perform frequent server pool updates during the attack, which is very likely since attacks can often last for many hours or even days. We are the first to propose LB schemes that guarantee high throughput of one million connections per second, while supporting a high pool update rate without breaking connections, and fighting against a high rate SYN attack, of up to 10 million fake SYNs per second.
	LB Scalability: Achieving the Right Balance Between Being Stateful and Stateless Reuven Cohen, Matty Kadosh, Alan Lo and Qasem Sayah Published in: IEEE/ACM Transactions on Networking, Vol. 30, No. 1, Feb. 2022 bibtex Abstract: A high performance Layer-4 load balancer (LB) is one of the most important components of a cloud service infrastructure. Such an LB uses network and transport layer information for deciding how to distribute client requests across a group of servers. A crucial requirement for a stateful LB is per connection consistency (PCC); namely, that all the packets of the same connection will be forwarded to the same server, as long as the server is alive, even if the pool of servers or the assignment function changes. The challenge is in designing a high throughput, low latency solution that is also scalable. This paper proposes a highly scalable LB, called Prism, implemented using a programmable switch ASIC. As far as we know, Prism is the first reported stateful LB that can process millions of connections per second and hundreds of millions connections in total, while ensuring PCC. This is due to the fact that Prism forwards all the packets in hardware, even during server pool changes, while avoiding the need to maintain a hardware state per every active connection. We implemented a prototype of the proposed architecture and showed that Prism can scale to 100 million simultaneous connections, and can accommodate more than one pool update per second.
	When the Network of a Smart City Is Not So Smart Reuven Cohen and Ali Tabaja Published in: IEEE Conference on Communications and Network Security (CNS), 2020 bibtex Abstract: In this paper we show that a simple repeated (ONOFF) jamming attack on a wireless distance vector protocol can have a global effect on the network and be as harmful as a sophisticated Network layer attack. This attack takes advantage of the nodes¿ limited awareness of topological changes when distance vector routing is used. To present the attack in a specific context, we consider the new RPL protocol, which plays an important role in the context of Smart City and Smart Utility networks. We describe the RPL approach to recover from link failures and show that this protocol is susceptible to the proposed attack. We also present a remedy technique and show that it can significantly alleviate the impact of the proposed attack.
	Cardinality Estimation in a Virtualized Network Device Using Online Machine Learning Reuven Cohen and Yuval Nezri Published in: IEEE/ACM Transactions on Networking, Vol. 27, No. 5, Oct. 2019 bibtex Abstract: Cardinality estimation algorithms receive a stream of elements, with possible repetitions, and return the number of distinct elements in the stream. Such algorithms seek to minimize the required memory and CPU resource consumption at the price of inaccuracy in their output. In computer networks, cardinality estimation algorithms are mainly used for counting the number of distinct flows, and they are divided into two categories: sketching algorithms and sampling algorithms. Sketching algorithms require the processing of all packets, and they are therefore usually implemented by dedicated hardware. Sampling algorithms do not require processing of all packets, but they are known for their inaccuracy. In this work we identify one of the major drawbacks of sampling-based cardinality estimation algorithms: their inability to adapt to changes in flow size distribution. To address this problem, we propose a new sampling-based adaptive cardinality estimation framework, which uses online machine learning.We evaluate our framework using real traffic traces, and show significantly better accuracy compared to the best known sampling-based algorithms, for the same fraction of processed packets.
	Inter-Datacenter Scheduling of Large Data Flows Reuven Cohen and Gleb Polevoy Published in: IEEE Transactions on Cloud Computing, Vol. 7, No. 1, 2019. bibtex Abstract: Inter-datacenter transfers of non-interactive but timely large flows over a private (managed) network is an important problem faced by many cloud service providers. The considered flows are non-interactive because they do not explicitly target the end users. However, most of them must be performed on a timely basis and are associated with a deadline. We propose to schedule these flows by a centralized controller, which determines when to transmit each flow and which path to use. Two scheduling models are presented in this paper. In the first, the controller also determines the rate of each flow, while in the second bandwidth is assigned by the network according to the TCP rules. We develop scheduling algorithms for both models and compare their complexity and performance.
	Bloom Hopping: Bloom filter based 2-Hop Neighbor Management in VANETs Florian Klingler, Reuven Cohen, Christoph and Falko Dressler Published in: IEEE Transactions on Mobile Computing, Vol. 18, No. 3, March 2019 bibtex Abstract: Recent works have shown that it would be beneficial for nodes in wireless networks with very dynamic topology to maintain a list of 2- hop neighbors, namely, the neighbors of its neighbors. This is important, for example, for routing, clustering, and message dissemination to all the nodes in a given geographic vicinity. In this paper, we propose a scheme that uses Bloom filters for maintaining 2-hop neighborship information. Furthermore, we developed a novel 2-hop broadcast algorithm making use of the specific nature of our Bloom filter encoded neighbor information. We particularly focus on the Vehicular Ad Hoc Networks (VANETs) application scenario. Here, beaconing is a periodic broadcast of awareness messages by each vehicle to its immediate neighbors. A naן approach would be to include all 2-hop neighbors in each beacon message, which, however, would work only for small or sparse scenarios. We show that our approach significantly reduces the length of the beacon messages, thereby keeping channel load and collision probability considerably lower than in the naן scheme. We further demonstrate the application of our Bloom filter based 2-hop neighbor table for developing higher layer protocols and introduce a multi-hop broadcast protocol called Bloom Hopping.
	Sampling-on-Demand in SDN Reuven Cohen and Evgeny Moroshko Published in: IEEE/ACM Transactions on Networking, Vol. 26, No. 6, Dec. 2018 bibtex Abstract: Sampling is an expensive network resource, because switches and routers are able to sample only a small fraction of the traffic they receive. Modern switches and routers perform uniform packet sampling, which has several major drawbacks: (i) the same flow might be unnecessarily sampled multiple times in different switches; (ii) all the flows traversing a switch whose sampling module is activated are sampled at the same rate; (iii) the sampling rate is fixed, even if the volume of the traffic changes. For the first time, we propose a sampling-on-demand monitoring framework. The proposed framework, presented as a component of SDN (Software Defined Network), adds a Sampling Management Module to the SDN controller. This module allows the controller to determine the sampling rate of each flow at each switch according to the monitoring goals of the network operator, while taking into account the monitoring capabilities of the switch. As part of the proposed framework, the paper defines a new optimization problem called SAP (Sampling Allocation Problem), which has to be solved by the Sampling Management Module in order to maximize the total sampling utility. The paper presents online and offline algorithms for solving this problem. It also presents three real network management applications, executed over Mininet, which are shown to significantly benefit from the proposed framework.
	Proactive Rerouting in Network Overlays Reuven Cohen, Yuval Dagan and Gabi Nakibly Published in: IFIP Networking 2018, Zurich, May 2018. bibtex Abstract: Virtual overlay network technology provides important benefits to large data centers and to service providers. These benefits include traffic isolation and ease of service provisioning. When the underlying network supports traffic engineering, tunneling brings another important benefit: the ability to control the exact route of all packets without handling each independent flow. This paper addresses the problem of rerouting when the core network supports traffic engineering. We introduce the novel concept of proactive (time-driven) rerouting, which we distinguish from the well-known concept of reactive (event-driven) rerouting. One important advantage of proactive rerouting is reducing the communication between the core network controller and the edge network controller. Another advantage is that new flows do not have to wait before they are admitted into a rerouted tunnel. Unlike a reactive rerouting algorithm that knows which tunnel has to be rerouted, a proactive rerouting algorithm does not receive as an input the identity of a specific tunnel. Thus, its main goal is to predict which tunnel to reroute in order to increase the probability that future flows will be accommodated. Our main contribution is the development of a proactive rerouting algorithm that performs very well, sometimes even better than the reactive algorithms.
	Not All VANET Broadcasts Are the Same: Context-Aware Class Based Broadcast Falko Dressler, Florian Klingler, Christoph Sommer and Reuven Cohen Published in: IEEE/ACM Transactions on Networking, . Vol. 26, No. 1, Feb. 2018, pp. 17 -- 30. bibtex Abstract: A major building block of Vehicular Ad Hoc Networks (VANETs) is broadcasting: the use of wireless communication for sharing information among vehicles, or between vehicles and infrastructure. Dozens of broadcast protocols have been developed in recent years, including protocols for 1-hop broadcasting of vehicle status information (beaconing) and for geocasting-based applications. However, most of these protocols were designed for one application and cannot co-exist, nor can one broadcast solution meet the demands of all applications. These observations motivated our effort to develop a holistic Network layer for VANETs. We identify the need for making VANET broadcast context-aware, and for supporting four different classes of broadcast protocols, each with its own properties. These classes are not only able to co-exist on the same Network layer, but also to complement one another’s functionality. Thus, large applications as well as more holistic Transport protocols can be designed by combining two or more broadcast classes. We discuss the specific characteristics of these classes and design candidate protocols for each class.
	A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection Reuven Cohen, Liran Katizr and Aviv Yehezkel Published in: KDD 2017, Halifax, Nova Scotia - Canada August 13 - 17, 2017 . bibtex Abstract: In recent years there has been a growing interest in developing "streaming algorithms" for efficient processing and querying of continuous data streams. These algorithms seek to provide accurate results while minimizing the required storage and the processing time, at the price of a small inaccuracy in their output. A fundamental query of interest is the intersection size of two big data streams. This problem arises in many different application areas, such as network monitoring, database systems, data integration and information retrieval. In this paper we develop a new algorithm for this problem, based on the Maximum Likelihood (ML) method. We show that this algorithm outperforms all known schemes and that it asymptotically achieves the optimal variance.
	Cardinality Estimation Meets Good-Turing Reuven Cohen, Liran Katizr and Aviv Yehezkel Published in: Elsevier Big Data Research journal, Vol. 9, Sept. 2017, pp. 1--8. . bibtex Abstract: Cardinality estimation algorithms receive a stream of elements whose order might be arbitrary, with possible repetitions, and return the number of distinct elements. Such algorithms usually seek to minimize the required storage and processing at the price of inaccuracy in their output. Real-world applications of these algorithms are required to process large volumes of monitored data, making it impractical to collect and analyze the entire input stream. In such cases, it is common practice to sample and process only a small part of the stream elements. This paper presents and analyzes a generic algorithm for combining every cardinality estimation algorithm with a sampling process. We show that the proposed sampling algorithm does not affect the estimator's asymptotic unbiasedness, and we analyze the sampling effect on the estimator's variance.
	Restorable Logical Topology in the Face of No or Partial Traffic Demand Knowledge Reuven Cohen and Gabi Nakibly Published in: IEEE/ACM Transactions on Networking, Vol. 24, No. 4, Aug. 2016, pp. 2074 -- 2085. . bibtex Abstract: The construction of a logical network on top of a physical (optical) infrastructure involves two intertwined tasks: logical link selection – deciding which pairs of routers will be connected by logical links (lightpaths), and logical link routing – deciding how to route each logical link across the optical network. The operator of such networks is often required to maximize the available throughput while guaranteeing its restorability. This paper is the first to combine these seemingly conflicting goals into one optimization criterion: maximizing the restorable throughput of the end-to-end paths. We address this problem in three cases: when the operator has no knowledge of the future bandwidth demands, when it has partial knowledge, and when it has full knowledge. We present efficient algorithms for each of these cases and use extensive simulations to compare their performance.
	Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes Reuven Cohen and Guy Grebla Published in: IEEE/ACM Transactions on Networking, Vol. 23, No. 6, Dec. 2015 . An earlier version was presented in: Infocom'2014 bibtex Abstract: LTE-advanced and other 4G cellular standards allow relay nodes (RNs) to be deployed as a substitute for base stations (BSs). Unlike a BS, an RN is not directly connected to the backbone. Rather, each RN is associated with a donor BS, to which it is connected through the OFDMA wireless link. A very important task in the operation of a wireless network is packet scheduling. In a network with RNs, such scheduling decisions must be made in each cell not only for the BS, but also for the RNs. Because the scheduler in a network with RNs must take into account the transmission resources of the BS and the RNs, it needs to find a feasible schedule that does not exceed the resources of a multi-dimensional resource pool. This makes the scheduling problem computationally harder than in a network without RNs. In this paper we define and study for the first time the packet-level scheduling problem for a network with RNs. This problem is shown to be not only NP-hard, but also very hard to approximate. To solve it, we propose an approximation with a performance guarantee, and a simple water-filling heuristic. Using simulations, we evaluate our new algorithms and show that they perform very well.
	Small Lies, Lots of Damage: a Partition Attack on Link-State Routing Protocols Reuven Cohen, Raziel Hess-Green and Gabi Nakibly Published in: IEEE Conference on Communications and Network Security (CNS), Florence, Italy, September 2015. . bibtex Abstract: The Internet consists of a large number of interconnected heterogeneous ASs (Autonomous Systems), each owned and administered by an autonomous organization. Traffic in each AS is forwarded by routers that maintain a coherent picture of the network topology using an intra-AS routing protocol. The most popular intra-AS routing protocols are link-state protocols, such as OSPF and IS-IS. An attacker who compromises a single AS router can send false routing advertisements. In the most simple and practical variant of the attack, the attacker falsifies only its own routing advertisements and not those of other routers. However, such an attack is widely considered to have limited effectiveness, because only a small part of the topology is falsified. In this paper we disprove this conception, by presenting and analyzing a new attack, referred to as a “partition attack,” which can cause extensive damage throughout the AS by causing routers to have an incoherent view of the AS topology. We investigate the computational complexity of the attack and show its effectiveness using extensive simulations. An important property of this attack is that it cannot be prevented even if LSAs are digitally signed.
	A Unified Scheme for Generalizing Cardinality Estimators to Sum Aggregation Reuven Cohen, Liran Katzir and Aviv Yehezkel Published in: Information Processing Letters (IPL), Volume 115, Issue 2, 336-342, February 2015.. bibtex Abstract: Cardinality estimation algorithms receive a stream of elements that may appear in arbitrary order, with possible repetitions, and return the number of distinct elements. Such algorithms usually seek to minimize the required storage at the price of inaccuracy in their output. This paper shows how to generalize every cardinality estimation algorithm that relies on extreme order statistics (min/max sketches) to a weighted version, where each item is associated with a weight and the goal is to estimate the total sum of weights. The proposed unified scheme uses the unweighted estimator as a black-box, and manipulates the input using properties of the beta distribution.
	Joint Scheduling and Fast Cell Selection in OFDMA Wireless Networks Reuven Cohen and Guy Grebla Published in: IEEE/ACM Transactions on Networking, Vol. 23, No. 1, Feb. 2015 . bibtex Abstract: In modern broadband cellular networks, the omni-directional antenna at each cell is replaced by 3 or 6 directional antennas, one in every sector. While every sector can run its own scheduling algorithm, bandwidth utilization can be significantly increased if a joint scheduler makes these decisions for all the sectors. This gives rise to a new problem, referred to as "joint scheduling," addressed in this paper for the first time. The problem is proven to be NP-hard, but we propose efficient algorithms with a worstcase performance guarantee for solving it. We then show that the proposed algorithms indeed substantially increase the network throughput.
	Optimizing Data Plane Resources for Multi-Path Flows Gabi Nakibly, Reuven Cohen and Liran Katzir Published in: IEEE/ACM Transactions on Networking, Vol. 23, No. 1, Feb. 2015 . bibtex Abstract: In many modern networks, such as datacenters, optical networks, and MPLS, the delivery of a traffic flow with a certain bandwidth demand over a single network path is either not possible or not cost effective. In these cases, it is very often possible to improve the network's bandwidth utilization by splitting the traffic flow over multiple efficient paths. While using multiple paths for the same traffic flow increases the efficiency of the network, it consumes expensive forwarding resources from the network nodes, such as TCAM entries of Ethernet/MPLS switches and wavelengths/lightpaths of optical switches. In this paper we define several problems related to splitting a traffic flow over multiple paths while minimizing the consumption of forwarding resources, and present efficient algorithms for solving these problems.
	Efficient Allocation of CQI Channels in Broadband Wireless Networks Reuven Cohen and Guy Grebla Published in: IEEE/ACM Transactions on Networking, Vol. 23, No. 2, April 2015 . An earlier version was presented in: IEEE Infocom'2011 mini-conference. bibtex Abstract: Advanced wireless technologies such as MIMO require each mobile node to send a lot of feedback to the base station. This feedback includes a Rank Indicator (RI), a Precoding Matrix Indicator (PMI), and a Channel Quality Indicator (CQI). All these indicators consume much of the uplink bandwidth, mainly because they are sent periodically. This expensive bandwidth is very often viewed as a major obstacle to the deployment of MIMO and other advanced closedloop wireless technologies. Therefore, the uplink bandwidth to these indicators must be allocated very carefully, while achieving certain optimization objectives. As far as we know, this paper is the first to propose a framework for the allocation of periodic feedback channels to the nodes of a wireless network. It also defines several relevant optimization problems and presents efficient algorithms for solving them. Finally, it presents a holistic scheme that indicates when the BS should invoke each of the proposed algorithms.
	On the Admission of Dependent Flows in Powerful Sensor Networks Reuven Cohen and Ilia Nudelman and Gleb Polevoy Published in: IEEE/ACM Transactions on Networking, Vol. 21, No. 5, Oct. 2013 . An earlier version was presented in: IEEE Infocom 2012, Orlando, Florida, March 2012. bibtex Abstract: In this paper we define and study a new problem, referred to as the Dependent Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the context of large-scale powerful (radar/camera) sensor networks, but we believe it has important applications on the admission of large flows in other networks as well. In order to optimize the selection of flows transmitted to the gateway, D-UFP takes into account possible dependencies between flows. We show that D-UFP is more difficult than NP-hard problems for which no good approximation is known. Then, we address two special cases of this problem: the case where all the sensors have a shared channel and the case where the sensors form a mesh and route to the gateway over a spanning tree.
	Locally vs. Globally Optimized Flow-Based Content Distribution to Mobile Nodes Mhameed Aezladen, Reuven Cohen and Danny Raz Published in: IEEE/ACM Transactions on Networking, Vol. 20, No. 5, Oct. 2012. An earlier version was presented in: IEEE Infocom 2009. bibtex Abstract: The paper deals with efficient distribution of timely information to flows of mobile devices. We consider the case where a set of Information Dissemination Devices (IDDs) broadcast a limited amount of information to passing mobile nodes that are moving along well-defined paths. This is the case, for example, in intelligent transportation systems. We develop a novel model that captures the main aspects of the problem, and define a new optimization problem we call MBMAP (Maximum Benefit Message Assignment Problem). We study the computational complexity of this problem in the global and local cases, and provide new approximation algorithms.
	Topology Maintenance in Asynchronous Sensor Networks Reuven Cohen and Boris Kapchits Published in: IEEE/ACM Transactions on Networking, Vol. 19, No. 1, Feb. 2011. An earlier version was presented in: SECON 2008. bibtex Abstract: In most sensor networks the nodes are static. Nevertheless, the node connectivity is subject to changes because of disruptions in wireless connectivity, transmission power changes, or loss of synchronization between neighboring nodes. Hence, even after a sensor is aware of its immediate neighbors, it must continuously maintain its view, a process we call topology maintenance. This work is the first to distinguish between neighbor discovery during sensor network initialization and topology maintenance. Whereas many works focus on the former task, we focus on the latter. We view topology maintenance as a joint task of all the connected sensors. Each sensor employs a simple protocol in a coordinate effort to reduce power consumption without increasing the time required to detect hidden sensors.
	Cross-Layer Hybrid FEC/ARQ Reliable Multicast with Adaptive Modulation and Coding in Broadband Wireless Networks Reuven Cohen, Guy Grebla and Liran Katzir Published in: IEEE/ACM Transactions on Networking, Vol. 18, No. 6, Dec. 2010. An earlier version was presented in: IEEE Infocom 2009. bibtex Abstract: In this paper we define and address a {\em new problem} that arises when a base station in a broadband wireless network wishes to multicast information to a large group of nodes and to guarantee some level of reliability using Application layer FEC codes. Every data block to be multicast is translated into a sequence of $K+n$ packets, from which every receiver must receive at least $K$ in order to correctly decode the block. The new problem is to determine which PHY layer MCS (Modulation and Coding Scheme) the base station should use for each packet. We present several variants of this problem, which differ in the number of ARQ (Automatic Repeat reQuest) rounds during which the delivery of a data block must be completed. Most of these variants are shown to be NP-hard. However, we present optimal solutions for practical instances, where the number of MCSs is small, and efficient approximations and heuristics for the general case of each variant.
	Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Scheduling Reuven Cohen and Liran Katzir Published in: IEEE/ACM Transactions on Networking, Vol. 18, No. 1, February 2010. An earlier version was presented in: IEEE Infocom 2008. bibtex Abstract: OFDMA is one of the most important modulation and access methods for the future mobile networks. Before transmitting a frame on the downlink, an OFDMA base station has to invoke an algorithm that determines which of the pending packets will be transmitted, what modulation should be used for each of them, and how to construct the complex OFDMA frame matrix as a collection of rectangles that fit into a single matrix with fixed dimensions. This paper proposes a scheme that solves this intricate OFDMA scheduling problem by breaking it down into two sub-problems, referred to as macro and micro scheduling.We analyze the computational complexity of these sub-problems and develop efficient algorithms for solving them.
	Maximizing Restorable Throughput in MPLS Networks Reuven Cohen and Gabi Nakibly Published in: IEEE/ACM Transactions on Networking, Vol. 18, No. 2, April 2010. An earlier version was presented in: IEEE Infocom 2008 mini-conference. bibtex Abstract: MPLS recovery mechanisms are increasing in popularity because they can guarantee fast restoration and high QoS assurance. Their main advantage is that their backup paths are established in advance, before a failure event takes place. Most research on the establishment of primary and backup paths has focused on minimizing the added capacity required by the backup paths in the network. However, this so-called Spare Capacity Allocation (SCA) metric is less practical for network operators who have a fixed capacitated network and want to maximize their revenues. In this paper we present a comprehensive study on restorable throughput maximization in MPLS networks. We present the first polynomialtime algorithms for the splittable version of the problem. For the unsplittable version, we provide a lower bound for the approximation ratio and propose an approximation algorithm with an almost identical bound. We present efficient heuristics which are shown to have excellent performance. One of our most important conclusions is that when one seeks to maximize revenue, local recovery should be the recovery scheme of choice.
	Traffic Engineering Considerations for the Placement of Network Services Reuven Cohen and Gabi Nakibly Published in: IEEE/ACM Transactions on Networking, Vol. 17, No. 2, April 2009. bibtex Abstract: Network services are provided by means of dedicated service gateways, through which traffic flows are directed. Existing work on service gateway placement has been primarily focused on minimizing the length of the routes through these gateways. Only limited attention has been paid to the effect these routes have on overall network performance. We propose a novel approach for the service placement problem, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow routes, we take advantage of these routes in order to enhance the overall network performance. We divide the problem into two sub-problems: finding the best location for each service gateway, and selecting the best service gateway for each flow. We propose efficient algorithms for both problems and study their performance. Our main contribution is showing that placement and selection of network services can be used as effective tools for traffic engineering.
	An Optimal Wake-Up Scheduling Algorithm for Minimizing Energy Consumption while Limiting Maximum Delay in a Mesh Sensor Network Reuven Cohen and Boris Kapchits Published in: IEEE/ACM Transactions on Networking, Vol. 17, No. 2, April 2009 (this is revised version of our Infocom 2007 paper, with a slightly different title). bibtex Abstract: This paper presents an algorithm for maximizing the lifetime of a sensor network while guaranteeing an upper bound on the end-to-end delay. We prove that the proposed algorithm is optimal, and that it requires simple computing operations that can be implemented by simple devices. To the best of our knowledge, this is the first paper to propose a sensor wake-up frequency that depends on the sensor's location in the routing paths. Using simulations, we show that the proposed algorithm significantly increases the lifetime of the network, while guaranteeing a maximum on the end-to-end delay.
	The Generalized Maximum Coverage Problem Reuven Cohen and Liran Katzir Published in: Information Processing Letters (IPL), Volume 108, Issue 1, 15 September 2008, Pages 15-22. bibtex Abstract: We define a new problem called the Generalized Maximum Coverage Problem (GMC). GMC is an extension of the Budgeted Maximum Coverage Problem, and it has important applications in wireless OFDMA scheduling. We use a variation of the greedy algorithm to produce a ($\frac{2e-1}{e-1}+\epsilon$)-approximation for every $\epsilon > 0$, and then use partial enumeration to reduce the approximation ratio to $\frac{e}{e-1}+\epsilon$.>
	On the Computational Complexity and Effectiveness of N-hub Shortest-Path Routing Reuven Cohen and Gabi Nakibli Published in: IEEE/ACM Transactions on Networking, Vol. 16, No. 3, June 2008. bibtex Abstract: In this paper we study the computational complexity and effectiveness of a concept we term "N-hub Shortest- Path Routing" in IP networks. N-hub Shortest-Path Routing allows the ingress node of a routing domain to determine up to N intermediate nodes ("hubs") through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Although this concept has been proposed in the past, this paper is the first to investigate it in depth. We apply N-hub Shortest-Path Routing to the problem of minimizing the maximum load in the network. We show that the resulting routing problem is NP-complete and hard to approximate. However, we propose eficient algorithms for solving it both in the online and the offline contexts. Our results show that N-hub Shortest-Path Routing can increase network utilization significantly even for N= 1. Hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the Internet.
	On the Trade-off Between Energy and Multicast Efficiency in 802.16e-like Mobile Networks Reuven Cohen, Liran Katzir and Romeo Rizzi Published in: IEEE Transactions on Mobile Computing Vol. 7, No. 3, pp. 346--357, March, 2008. bibtex Abstract: In this paper we define a new problem that has not been addressed in the past: the trade-off between energy efficiency and throughput for multicast services in 802.16e or similar mobile networks. In such networks, the mobile host can reduce its energy consumption by entering the sleep mode when it is not supposed to receive or transmit information. For unicast applications the trade-off between delay and energy efficiency has been extensively researched. However, for mobile hosts running multicast (usually push-based) applications, it is much more difficult to determine when data should be transmitted by the base-station and when each host should enter the sleep mode. In order to maximize the channel throughput while limiting energy consumption, a group of hosts needing similar data items should be active during the same time intervals. We define this as an optimization problem, and present several algorithms for it. We show that the most efficient solution is the one that employs cross-layer optimization by dividing the hosts into groups according to the quality of their downlink PHY channels.
	A Generic Quantitative Approach to the Scheduling of Synchronous Packets in a Shared Uplink Wireless Channel Reuven Cohen and Liran Katzir Published in: IEEE/ACM Transactions on Networking ,Vol. 15, No. 4, pp. 932-943, Aug. 2007. bibtex Abstract: The scheduling logic at the base station of a shared wireless medium supports time-dependent (synchronous) applications by allocating timely transmission grants. To this end it must take into account not only the deadlines of the pending packets, but also the channel conditions for each potential sender, the requirements of non-synchronous applications, and the packet retransmission strategy. With respect to these factors, we identify three scheduling scenarios and show that the scheduler logic faces a different challenge in addressing each of them. We then present a generic scheduling algorithm that translates all the factors relevant to each scenario into a common profit parameter, and selects the most profitable transmission instances.
	The Global-ISP Paradigm Reuven Cohen and Amnon Shochot Published in: Computer networks , Vol. 51, No. 8, pp. 1908 -- 1921, June 2007. bibtex Abstract: We present a new paradigm, called "Global ISP" (G-ISP). Its goal is to solve, or at least alleviate, problems of inter-domain routing, such as slow convergence, and lack of QoS and multicast support. One of the most important properties of the proposed paradigm is that it can be gradually deployed on the Internet. A G-ISP can be viewed as an additional ISP that provides transit services to its customers over an overlay network. Because a G-ISP differs from a "regular" ISP, some extension to the standard BGP protocol is required. This extension and its effects on the BGP protocol are described in this paper Algorithms for building a G-ISP overlay network and their applications are also presented.
	An Efficient Approximation for the Generalized Assignment Problem Reuven Cohen, Liran Katzir and Danny Raz Published in: Information Processing Letters (IPL), Volume 100, No. 4, pp. 162 -- 166, Nov. 2006. bibtex Abstract: We present a simple family of algorithms for solving the Generalized Assignment Problem (GAP). Our technique is based on a novel combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for GAP. If the approximation ratio of the knapsack algorithm is $\alpha$ and its running time is $O(f(\n))$, our algorithm guarantees a $(1+\alpha)$ approximation ratio, and it runs in $O(\m \cdot f(\n)+\m \cdot \n)$, where $\n$ is the number of items and $\m$ is the number of bins. Not only does our technique comprise a general interesting framework for the GAP problem; it also matches the best combinatorial approximation for this problem, with a much simpler algorithm and a better running time.
	On the Establishment of Access-VPN in Broadband Access Networks Reuven Cohen Published in: IEEE Communications Magazine, Vol. 41 No. 2 , pp. 156--163, February 2003. bibtex Abstract: Many corporate networks use the Internet as a cost-effective substitute for expensive leased lines and long-distance telephone calls, for allowing their users to have on-demand connectivity into their intranets through ad hoc tunnels, a concept known as access VPN. Establishing an access VPN in a broadband access network is very often a difficult networking challenge that requires several tunnels to be established between the various involved entities. This is especially the case in an open broadband access network where the association between a host and its ISP is not known to the network in advance. This article discusses several schemes for establishing an access VPN in a broadband access network, and explains the need for the various tunnels in each scheme.
	Crankback Prediction in Hierarchical ATM networks Eyal Felstine, Reuven Cohen and Ofer Hadar Published in: Journal of Network and Systems Management, Vol. 10, No. 3, September 2002. bibtex Abstract: When an ATM node discovers that it cannot continue the setup of a virtual channel under the requested Quality of Service (QoS), it initiates a backtracking procedure called "crankback." We propose a novel scheme, referred to as crankback prediction, that decreases the crankback overhead. Under the proposed scheme, nodes check during the connection admission control procedure whether the establishment of a virtual channel has a good chance to be admitted over the entire designated route. If this is not the case, crankback is initiated even before a particular QoS parameter is violated. The main idea behind the proposed scheme is to allocate a "quota" to the Peer Groups (PGs) along the message path, and then to suballocate this quota to the child PGs of these PGs. This process continues recursively until reaching the 1-level PG, which contains only physical nodes. The main advantage of the proposed scheme is that it lowers the setup delay and the processing and communication load imposed by signaling messages that establish unused portions of Virtual Channels (VCs).
	A Dynamic Approach for Efficient TCP Buffer Allocation Amit Cohen and Reuven Cohen Published in: IEEE Transactions on Comp,Vol. 51 No. 3 pp. 303-312, March 2002. bibtex Abstract: The paper proposes local and global optimization schemes for eficient TCP buffSer allocation in an HTTP server. The proposed local optimization scheme dynamically adjusts the TCP send-buffer size to the connection and server characteristics. The global optimization scheme divides a certain amount of buffer space among all active TCP connections. These schemes are of increasing importance due to the large scale of TCP connection characteristics. The schemes are compared to the static allocation policy employed by a typical HTTP server, and shown to achieve considerable improvement to server performance and better utilization of its resources. The schemes require only minor code changes and only at the server.
	Balanced packet Discard for improving TCP Performance in ATM Networks Reuven Cohen and Yaniv Hamo Published in: Computer Communications, Vol. 24, No. 15-16, pp. 1525-1539. bibtex Abstract: TCP suffers from low performance over Asynchronous Transfer Mode (ATM) networks. This is mainly because during phases of congestion, ATM drops cells without taking into account the effect this has on the upper layer protocols. Two main algorithms, called PPD and EPD, were proposed in the past for improving TCP performance. However, they address one aspect of the problem, that has only small effect on the final performance. In this paper we propose an enhanced method for packet discard, called Balanced Packet Discard (BPD), that improves TCP performance dramatically on congested networks and guarantees fairness among multiple connections. We will show that BPD increases TCP throughput by more than 25\% compared to EPD/PPD.
	PCRTT Enhancement for Off-Line Video Smoothing Ofer Hadar Reuven Cohen Published in: The Journal of Real Time Imaging, Vol. 7, No. 3, pp. 301-314, June 2001. bibtex Abstract: An enhancement of the Piecewise Constant Rate Transmission and Transport (PCRTT) algorithm for reducing the burstiness of a video stream based on smoothing constant intervals is proposed. The new algorithm, called E-PCRTT, relies on geometrical considerations rather than traditional rate-control analysis. E-PCRTT is shown to construct transmission rate-plans with smaller buffer sizes, as compared to the original PCRTT, and alternatively, for the same buffer size, e-PCRTT reduces the number of bandwidth changes compared to PCRTT. In addition, E-PCRTT produces a rate-plan that requires a smaller initial playback delay.
	On the Cost of Virtual Private Networks Reuven Cohen and Gideon Kaempfer Published in: IEEE/ACM Transactions on Networking,Vol. 8 No. 6, Dec. 2000. bibtex Abstract: A virtual private network (VPN) is a private data network that uses a nonprivate data network to carry traffic between remote sites. An "Intranet VPN" establishes network layer connectivity between remote Intranet sites by creating an IP overlay network over the nonprivate network, using various tunneling mechanisms. There are two approaches for establishing such tunnels: a "CPE-based approach" and a "network-based approach." In the first approach, tunnels are established only between the CPE devices, whereas in the second approach tunnels are also established between the routers of the core nonprivate network. In this paper we address the problem of determining a CPE-based and a network- based layout of VPN tunnels while taking into account two factors: the cost of the links over which the VPN tunnels are established and the cost of the core routers that serve as end points for the VPN.We define related graph algorithm problems, analyze their complexity, and present heuristics for solving these problems efficiently.
	Schemes for Scheduling of Control Messages by Hierarchical Protocols Edi Bortnikov and Reuven Cohen Published in: Computer Communications,Vol. 22 No. 5, May 1999. bibtex Abstract: The paper addresses the problem of designing efficient scheduling policies for the transmission of control messages by hierarchical network protocols. Such protocols encounter a tradeoff between the desire to forward a control message across the tree as soon as it is received, and the desire to reduce control traffic. Scheduling problems that arise in this context are defined and discussed. The paper mainly concentrates on minimizing the average extra delay encountered by the control messages under an upper bound on the number of outgoing messages a node can send during a fixed period of time. A polynomial-time algorithm is presented for the off-line version of the problem, and then several efficient on-line heuristics are presented and compared.
	On the Distribution of Routing Computation in Hierarchical ATM Networks Eyal Felstine and Reuven Cohen Published in: IEEE/ACM Transactions on Networking, Vol. 7 No. 6, pp.906-916, Dec. 1999. bibtex Abstract: ATM PNNI (Private Network-to-Network Interface) is a hierarchical and dynamic link-state routing protocol, designed to scale to the largest possible ATM networks, encompassing thousands of nodes. The paper investigates the route computation load imposed by the PNNI routing scheme, and shows that this load is unevenly distributed among the network nodes. More specifically, the routing computation load associated with the set up of a single VC grows exponentially with the hierarchy level. As a result, some of the network nodes { mainly those that function as border nodes of high levels { may be overloaded with route computation, while other nodes are rarely involved in this process. The paper also proposes a possible scheme for spreading the route computation burden more evenly. According to this scheme, heavily loaded nodes transfer route computation tasks to lightly loaded nodes.
	Service Provisioning in an ATM-over-ADSL Access Network Reuven Cohen Published in: IEEE Communications Magazine, Vol. 37 No. 10, pp. 82-87, Oct. 1999. bibtex Abstract: Asymmetric Digital Subscriber Loop (ADSL) technology is a new platform for delivering broadband services to homes and small businesses, thus bringing the information highway to the mass market. Successful deployment of an ADSL-based access network is not only a matter of delivering faster rates, but also offering solutions that are cost-effective and easy to use and to manage. As deregulation and competition spread globally, an ADSL-based access network should also enable end users to choose their service providers dynamically, and to switch from one provider to another easily and rapidly, even on a real-time basis. In light of these requirements, the paper addresses the issue of service provisioning in an ATM-over-ADSL access network. It concentrates on the provisioning of services using the PPP protocol. PPP is the common protocol for service provisioning in circuit-switched telephone networks. However, it is also considered as a good choice for the delivery of broadband services since it has builtin mechanisms for IP address assignment, layer-2 security and AAA (Authentication, Authorization and Accounting). The paper presents the problem of initiating a PPP connection at an Ethernet-based host. It presents several solutions for this problem and discusses the advantages and disadvantages of each solution.
	An Efficient Scheme for Accommodating Synchronous Traffic in a Cable-Modem Network While Avoiding Segmentation of Asynchronous Packets Reuven Cohen Published in: Computer Communications, Vol. 22 No. 5, pp. 399-410, April 1999. bibtex Abstract: Cable-modem (CM) technology is being developed to provide high-speed multimedia services to the subscribers' homes over the existing hybrid-fiber-coax (HFC) infrastructure of cable TV networks. The paper proposes an eficient scheme for combining asynchronous and synchronous traffic on the upstream channel of a CM network when segmentation of the asynchronous packets is to be avoided, e.g. because of cost considerations. The new scheme guarantees the synchronous sources the same quality of service provided by the FDDI timed token protocol. That is, a guaranteed average delay between consecutive transmissions, a guaranteed maximum delay between consecutive transmissions, and a guaranteed bandwidth on the upstream channel.
	High Speed Internet Access Through Unidirectional Geostationary Satellite Channels Ina Minei and Reuven Cohen Published in: IEEE Journal on Selected Areas in Communications, Vol. 17 No. 2, February 1999. bibtex Abstract: One of the proposed solutions for increasing the speed of Internet access is to connect the home user to a direct satellite channel, at a speed 20 times faster than that of an average telephone modem. Communication over satellite links is often characterized by sporadic high bit-error rates and burst losses. This is especially true when working in the Ka band, where weather conditions greatly affect link availability. Under such conditions, the TCP protocol that is predominantly used by data applications, degrades dramatically in performance. Using simulations, this paper studies the performance of TCP under different network conditions. Several modifications, that take advantage of the special properties of the satellite channel, are proposed and a new sender algorithm which can eficiently handle burst losses is presented. The main attractiveness of the proposed new sender algorithm is that it can be implemented only at the satellite ground station, rather than at every server in the world.
	Restricted Dynamic Steiner Trees for Scalable Multicast in Datagram Networks Ehud Aharoni and Reuven Cohen Published in: IEEE/ACM Transactions on Networking, Vol. 6 No. 3, pp. 286 -- 297 June 1998. bibtex Abstract: The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree.
	Tuning TCP for High Performance in Hybrid Fiber Coaxial Broadband Access Networks Reuven Cohen and Srinivas Ramanathan Published in: IEEE/ACM Transactions on Networking, Vol. 6 No. 1, Feb. 1998. bibtex Abstract: Motivated by the phenomenal growth of the Internet in recent years, a number of cable operators are in the process of upgrading their cable networks to offer data services to residential subscribers, providing them direct access to a variety of community content as well as to the Internet. Using cable modems that implement sophisticated modulation-demodulation circuitry, these services promise to offer a several hundred-fold increase in access speeds to the home compared to conventional telephone modems. Initial experiences indicate that cable networks are susceptible to a variety of radio-frequency impairments that can result in significant packet loss during data communication. In the face of such losses, the TCP protocol that is predominantly used by data applications degrades dramatically in performance. Consequently, subscribers of broadband data services may not perceive the projected hundred fold increase in performance. In this paper, we analyze the performance of TCP under different network conditions using simulations and propose simple modifications that can offer up to three-fold increase in performance in access networks that are prone to losses. These modifications require only minor changes to TCP implementations at the local network servers alone (and not at subscribers' PCs).
	Using Proxies to Enhance TCP Performance over Hybrid Fiber Coaxial Networks Reuven Cohen and Srinivas Ramanathan Published in: Computer Communications,Vol. 20 No. 16, January 1998. bibtex Abstract: Using cable modems that operate at several hundred times the speed of conventional telephone modems, many cable operators are beginning to offer World Wide Web access and other data services to residential subscribers. Initial experiences indicate that real-world Hybrid Fiber Coaxial (HFC) networks are susceptible to a variety of radio-frequency impairments that significantly reduce the benefits of using high-speed cable modems. The effects of packet losses in the access network are particularly accentuated during subscriber accesses to remote servers on the Internet. The longer round-trip times in such accesses together with the high packet loss rate result in dramatic degradations in performance perceived by subscribers. This paper shows that by using proxy servers to handle all remote accesses from an HFC access network, the performance of remote accesses can be significantly enhanced even in cases when the proxy servers do not function as data caches. By handling packet losses that occur in the HFC network locally, at low latencies and without the remote server even being aware of the loss, a proxy server enables faster recovery from packet losses. Most importantly, since it controls data transmissions over the local HFC network, the proxy server's TCP implementation can be optimized for the loss characteristics of the HFC access network, enabling a significant increase in performance when the access network is lossy.
	An Efficient Approach for Token-Ring LAN Emulation over ATM Reuven Cohen and Eli Stein Published in: Computer Communications,Vol. 20 No. 13, November 1997. bibtex
	ATM Connectionless Routing over Sink Trees Reuven Cohen, Baiju Patel, Frank Schaffa and Mark Willebeek-LeMair Published in: IEEE/ACM Transactions on Networking , Vo. 4, No. 3, June 1996. bibtex
	Video On Demand Session Management Reuven Cohen and Y. Chang Published in: IEEE Journal on Selected Areas in Communications, Vol. 14, No. 6, Aug. 1996. bibtex
	Handover in a Micro-Cell Packet Switched Mobile Network Reuven Cohen, Baiju Patel and Adrian Segall Published in: ACM Journal of Wireless Networks, Vol. 2, No. 1, 1996. bibtex
	Reliable Transmission of Data over an Unreliable Semi-FIFO Routing Layer Reuven Cohen and Yoram Ofek Published in: Computer Networks and ISDN Systems, Vol. 27, No. 12, Nov. 1995. bibtex
	A New Label-Based Source Routing for Multi-Ring Networks Reuven Cohen, Yoram Ofek and Adrian Segall Published in: IEEE/ACM Transactions on Networking, Vol. 3 No. 3, June. 1995. bibtex
	Label Swapping With Self-Termination in ATM Networks Reuven Cohen and Yoram Ofek Published in: IEEE/ACM Transactions on Networking,Vol. 2 No. 5, Oct. 1994. bibtex
	Session Swapping: A New Approach for Optimal Bandwidth Sharing of Circuit Switched Channels Reuven Cohen Published in: IEEE/ACM Transactions on Networking, Vol. 2 No. 3, June 1994. bibtex
	Multiple Logical Token-Rings in a Single High-Speed Ring Reuven Cohen and Adrian Segall Published in: IEEE Transactions on Communications, Vol. 42, No. 4, April 1994. bibtex
	A New Protocol for Route Discovery in Multiple-Ring Networks: Part II --- Multicast Source Routing, Recovery and High-Speed Processing Reuven Cohen and Adrian Segall Published in: IEEE Transactions on Communications,, Vol. 42, No. 3, March 1994. bibtex
	A New Protocol for Route Discovery in Multiple-Ring Networks: Part I --- The Basic Protocol Reuven Cohen and Adrian Segall Published in: IEEE Transactions on Communications, Vol. 42, No. 2, Feb. 1994. bibtex
	An Efficient Priority Mechanism for Rings Reuven Cohen and Adrian Segall Published in: IEEE Transactions on Communications, Vol. 42, No. 4, April 1994. bibtex
	One-Bit-Delay in Ring Networks Reuven Cohen Published in: IEEE Transactions on Computers, Volume 42, No. 6, June 93. bibtex
	A New Scheme for Dynamic Management of Isochronous Channels in Integrated Rings Reuven Cohen and Adrian Segall Published in: Computer Networks and ISDN Systems, Volume 24 (1992), Number 2, 131-144. bibtex
	An Efficient Reliable Ring Protocol Reuven Cohen and Adrian Segall Published in: IEEE Transactions on Communications, Vol. 39, No. 11, Nov. 1991. bibtex
Conference Papers
	On the Admission of Dependent Flows in Powerful Sensor Networks Reuven Cohen and Ilia Nudelman and Gleb Polevoy Presented in: IEEE Infocom 2012, Orlando, Florida, March 2012. bibtex Abstract: In this paper we define and study a new problem, referred to as the Dependent Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the context of large-scale powerful (radar/camera) sensor networks, but we believe it has important applications on the admission of large flows in other networks as well. In order to optimize the selection of flows transmitted to the gateway, D-UFP takes into account possible dependencies between flows. We show that D-UFP is more difficult than NP-hard problems for which no good approximation is known. Then, we address two special cases of this problem: the case where all the sensors have a shared channel and the case where the sensors form a mesh and route to the gateway over a spanning tree.
	Handovers with Forward Admission Control for Adaptive TCP Streaming in LTE-Advanced with Small Cells Reuven Cohen and Anna Levin Presented in: IEEE ICCCN 2012, Munich, Germany, July 2012. bibtex Abstract: An important trend in the evolution of cellular networks is the introduction of cost efficient small cells. However, most of these cells will have only wireless connectivity to the backbone.Consequently, handovers will be needed much more frequently and the bandwidth between neighboring cells will become a scarce resource. Both problems are likely to affect one of the most fast growing cellular applications: adaptive TCP video streaming. While the high handover rate is likely to have a negative impact on TCP streaming due to packet loss during handovers, solutions that forward packets from the old cell to the new one must limit the amount of wireless bandwidth they use. This trade-off is addressed in the following paper.
	Energy-Delay Optimization in an Asynchronous Sensor Network with Multiple Gateways Reuven Cohen and Boris Kapchits Presented in: SECON 2011, Salt Lake City, Utah, June 2011. bibtex Abstract: This paper studies the problem of energy efficient routing in a sensor network with multiple gateways. Due to the complexity of this problem, we divide it into two subproblems: the problem of constructing efficient routing trees and the problem of wake-up frequency assignment in a network with multiple routing trees. For the first problem we present an optimal algorithm and an approximation algorithm that achieves very close performance but can be more easily implemented. We prove that the second problem is NP-hard and propose a polynomial time approximation algorithm.
	Efficient Allocation of CQI Channels in Broadband Wireless Networks Reuven Cohen and Guy Grebla Presented in: IEEE Infocom'2011 mini-conference. bibtex Abstract: Advanced wireless technologies such as MIMO require each mobile node to send a lot of feedback to the base station. This feedback includes a Rank Indicator (RI), a Precoding Matrix Indicator (PMI), and a Channel Quality Indicator (CQI). All these indicators consume much of the uplink bandwidth, mainly because they are sent periodically. This expensive bandwidth is very often viewed as a major obstacle to the deployment of MIMO and other advanced closedloop wireless technologies. Therefore, the uplink bandwidth to these indicators must be allocated very carefully, while achieving certain optimization objectives. As far as we know, this paper is the first to propose a framework for the allocation of periodic feedback channels to the nodes of a wireless network. It also defines several relevant optimization problems and presents efficient algorithms for solving them. Finally, it presents a holistic scheme that indicates when the BS should invoke each of the proposed algorithms.
	A Scalable Scheme for Preventing Feedback Implosion in a Large-Scale Multi-Tier Sensor Network Reuven Cohen and Alexander Landau Presented in: IEEE SECON 2010, Boston, Massachusetts , June 2010. bibtex Abstract: We consider a huge hierarchical sensor network consisting of millions of sensors arranged in clusters for scalability and cost-performance. We address the problem of how a centralized gateway can estimate the number of sensors affected by a certain event. We propose a scheme for solving this problem in the most efficient way in terms of communication cost, and a complete mathematical analysis of the estimation error. We show that the error of the new scheme is very small even if the number of sensors experiencing an event is several million.
	A Route-Control Mechanism for Improving the Performance of Transport Protocols in a MANET Reuven Cohen and Anya Levin Presented in: the 34th Annual IEEE Conference on Local Computer Networks (LCN), Zurich, Switzerland, Oct. 2009. bibtex Abstract: We propose a new cross-layer mechanism, referred to as Route-control, for mobile ad-hoc networks (MANETs). This mechanism, which works in the Network and Transport layers, aims at enhancing the performance of MANETs' reliable Transport protocols. The main idea behind the proposed mechanism is to notify the sender when the packets of a Transport layer flow change their route. We show that the sender can benefit from this information when deciding whether to retransmit a missing segment or to wait, when estimating the RTT (Round Trip Time), and when deciding whether to change the congestion window.
	Locally vs. Globally Optimized Flow-Based Content Distribution to Mobile Nodes Mhameed Aezladen, Reuven Cohen and Danny Raz Presented in: IEEE Infocom 2009. bibtex Abstract: The paper deals with efficient distribution of timely information to flows of mobile devices. We consider the case where a set of Information Dissemination Devices (IDDs) broadcast a limited amount of information to passing mobile nodes that are moving along well-defined paths. This is the case, for example, in intelligent transportation systems. We develop a novel model that captures the main aspects of the problem, and define a new optimization problem we call MBMAP (Maximum Benefit Message Assignment Problem). We study the computational complexity of this problem in the global and local cases, and provide new approximation algorithms.
	Cross-Layer Hybrid FEC/ARQ Reliable Multicast with Adaptive Modulation and Coding in Broadband Wireless Networks Reuven Cohen, Guy Grebla and Liran Katzir Presented in: IEEE Infocom 2009. bibtex Abstract: In this paper we define and address a {\em new problem} that arises when a base station in a broadband wireless network wishes to multicast information to a large group of nodes and to guarantee some level of reliability using Application layer FEC codes. Every data block to be multicast is translated into a sequence of $K+n$ packets, from which every receiver must receive at least $K$ in order to correctly decode the block. The new problem is to determine which PHY layer MCS (Modulation and Coding Scheme) the base station should use for each packet. We present several variants of this problem, which differ in the number of ARQ (Automatic Repeat reQuest) rounds during which the delivery of a data block must be completed. Most of these variants are shown to be NP-hard. However, we present optimal solutions for practical instances, where the number of MCSs is small, and efficient approximations and heuristics for the general case of each variant.
	"Not All At Once!" - A Generic Scheme for Estimating the Number of Affected Nodes Reuven Cohen and Alexander Landau Presented in: IEEE Infocom'2009 mini-conference. bibtex Abstract: We present a generic scheme for estimating the size of a group of nodes affected by the same event in a large-scale network, such as a grid, a sensor network or a wireless broadband access network, while receiving only a small number of feedback messages from this group. Using the proposed scheme, a centralized gateway analyzes the transmission times of these feedback messages, defines a likelihood function for them, and then uses the Newton-Raphson method to find the number of affected nodes for which this function is maximized. We present complete mathematical analysis for the precision of the proposed algorithm and provide tight upper and lower bounds for the estimation error. These bounds allow us to improve the precision of our estimation.
	Topology Maintenance in Asynchronous Sensor Networks Reuven Cohen and Boris Kapchits Presented in: IEEE SECON 2008, San-Francisco. bibtex Abstract: In most sensor networks the nodes are static. Nevertheless, the node connectivity is subject to changes because of disruptions in wireless connectivity, transmission power changes, or loss of synchronization between neighboring nodes. Hence, even after a sensor is aware of its immediate neighbors, it must continuously maintain its view, a process we call topology maintenance. This work is the first to distinguish between neighbor discovery during sensor network initialization and topology maintenance. Whereas many works focus on the former task, we focus on the latter. We view topology maintenance as a joint task of all the connected sensors. Each sensor employs a simple protocol in a coordinate effort to reduce power consumption without increasing the time required to detect hidden sensors.
	Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Scheduling Reuven Cohen and Liran Katzir Presented in: IEEE Infocom 2008. bibtex Abstract: OFDMA is one of the most important modulation and access methods for the future mobile networks. Before transmitting a frame on the downlink, an OFDMA base station has to invoke an algorithm that determines which of the pending packets will be transmitted, what modulation should be used for each of them, and how to construct the complex OFDMA frame matrix as a collection of rectangles that fit into a single matrix with fixed dimensions. This paper proposes a scheme that solves this intricate OFDMA scheduling problem by breaking it down into two sub-problems, referred to as macro and micro scheduling.We analyze the computational complexity of these sub-problems and develop efficient algorithms for solving them.
	Maximizing Restorable Throughput in MPLS Networks Reuven Cohen and Gabi Nakibly Presented in: IEEE Infocom 2008 mini-conference. bibtex Abstract: MPLS recovery mechanisms are increasing in popularity because they can guarantee fast restoration and high QoS assurance. Their main advantage is that their backup paths are established in advance, before a failure event takes place. Most research on the establishment of primary and backup paths has focused on minimizing the added capacity required by the backup paths in the network. However, this so-called Spare Capacity Allocation (SCA) metric is less practical for network operators who have a fixed capacitated network and want to maximize their revenues. In this paper we present a comprehensive study on restorable throughput maximization in MPLS networks. We present the first polynomialtime algorithms for the splittable version of the problem. For the unsplittable version, we provide a lower bound for the approximation ratio and propose an approximation algorithm with an almost identical bound. We present efficient heuristics which are shown to have excellent performance. One of our most important conclusions is that when one seeks to maximize revenue, local recovery should be the recovery scheme of choice.
	To Drop or Not to Drop: On the Impact of Handovers on TCP Performance Reuven Cohen and Anna Levin Presented in: MOVE 2008. bibtex Abstract: This paper presents a comparison between two handover schemes: drop and forward. In the drop scheme, packets received by the base station after the host has disconnected are dropped, whereas in the forward scheme these packets are forwarded to the new base station. We analyze various TCP flavors and compare our findings to simulation results. Our results can be used to determine which handover scheme and which TCP flavor should be employed to minimize the negative effect of handovers on TCP performance.
	An Optimal Algorithm for Minimizing Energy Consumption while Limiting Maximum Delay in a Mesh Sensor Network Reuven Cohen and Boris Kapchits Presented in: IEEE Infocom 2007. An enhanced version of this paper with a slightly different title, has been accepted to IEEE/ACM Transactions on Networking. bibtex Abstract: This paper presents an algorithm for maximizing the lifetime of a sensor network while guaranteeing an upper bound on the end-to-end delay. We prove that the proposed algorithm is optimal, and that it requires simple computing operations that can be implemented by simple devices. To the best of our knowledge, this is the first paper to propose a sensor wake-up frequency that depends on the sensor's location in the routing paths. Using simulations, we show that the proposed algorithm significantly increases the lifetime of the network, while guaranteeing a maximum on the end-to-end delay.
	Traffic Engineering Considerations for the Placement of Network Services Reuven Cohen and Gabi Nakibly Presented in: IEEE Infocom 2007. An enhanced version of this paper has been accepted to IEEE/ACM Transactions on Networking.. bibtex Abstract: Network services are provided by means of dedicated service gateways, through which traffic flows are directed. Existing work on service gateway placement has been primarily focused on minimizing the length of the routes through these gateways. Only limited attention has been paid to the effect these routes have on overall network performance. We propose a novel approach for the service placement problem, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow routes, we take advantage of these routes in order to enhance the overall network performance. We divide the problem into two sub-problems: finding the best location for each service gateway, and selecting the best service gateway for each flow. We propose efficient algorithms for both problems and study their performance. Our main contribution is showing that placement and selection of network services can be used as effective tools for traffic engineering.
	On the Trade-off Between Energy and Multicast Efficiency in 802.16e-like Mobile Networks Reuven Cohen and Romeo Rizzi Presented in: IEEE Infocom 2006. An enhanced version of this paper has been accepted to IEEE Transactions on Mobile Computing. bibtex Abstract: In this paper we define a new problem that has not been addressed in the past: the trade-off between energy efficiency and throughput for multicast services in 802.16e or similar mobile networks. In such networks, the mobile host can reduce its energy consumption by entering the sleep mode when it is not supposed to receive or transmit information. For unicast applications the trade-off between delay and energy efficiency has been extensively researched. However, for mobile hosts running multicast (usually push-based) applications, it is much more difficult to determine when data should be transmitted by the base-station and when each host should enter the sleep mode. In order to maximize the channel throughput while limiting energy consumption, a group of hosts needing similar data items should be active during the same time intervals. We define this as an optimization problem, and present several algorithms for it. We show that the most efficient solution is the one that employs cross-layer optimization by dividing the hosts into groups according to the quality of their downlink PHY channels.
	A Generic Quantitative Approach to the Scheduling of VoIP Packets in a Shared Medium Wireless Access Network Reuven Cohen and Liran Katzir Presented in: IEEE Infocom 2004. An enhanced version of this paper appears in IEEE/ACM Transactions on Networking. bibtex Abstract: The scheduling logic at the base station of a shared wireless medium supports time-dependent (synchronous) applications by allocating timely transmission grants. To this end it must take into account not only the deadlines of the pending packets, but also the channel conditions for each potential sender, the requirements of non-synchronous applications, and the packet retransmission strategy. With respect to these factors, we identify three scheduling scenarios and show that the scheduler logic faces a different challenge in addressing each of them. We then present a generic scheduling algorithm that translates all the factors relevant to each scenario into a common profit parameter, and selects the most profitable transmission instances.
	On the Computational Complexity and Effectiveness of N-hub Shortest-Path Routing Reuven Cohen and Gabi Nakibli Presented in: IEEE Infocom 2004. An enhanced version of this paper has been accepted to IEEE/ACM Transactions on Networking. bibtex Abstract: In this paper we study the computational complexity and effectiveness of a concept we term "N-hub Shortest- Path Routing" in IP networks. N-hub Shortest-Path Routing allows the ingress node of a routing domain to determine up to N intermediate nodes ("hubs") through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Although this concept has been proposed in the past, this paper is the first to investigate it in depth. We apply N-hub Shortest-Path Routing to the problem of minimizing the maximum load in the network. We show that the resulting routing problem is NP-complete and hard to approximate. However, we propose eficient algorithms for solving it both in the online and the offline contexts. Our results show that N-hub Shortest-Path Routing can increase network utilization significantly even for N=1. Hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the Internet.
	Scheduling Algorithms for a Cache Pre-Filling Content Distribution Network Reuven Cohen, Liran Katzir and Danny Raz Presented in: IEEE Infocom 2002. bibtex Abstract: Cache pre-filling is emerging as a new concept for increasing the availability of popular web items in cache servers. According to this concept, web items are sent by a "push-server" to the proxy cache servers, usually through a broadcast-based or a multicast-based distribution mechanism. One of the most difficult challenges is to design the scheduling algorithm of the push-server. This algorithmneeds to determine the "broadcast scheduling map", namely which web items to broadcast and when. In this paper we study the approach where every constant period of time each proxy cache analyzes the requests it has received in the past and determines which web item it prefers to receive by broadcast and when. We formalize a related problem, called the "Cache Pre-filing Push" (CPFP) problem, analyze its computational complexity, and describe efficient algorithms to solve it.
	The "Last-Copy" Approach for Distributed Cache Pruning in a Cluster of HTTP Proxies Reuven Cohen and Itai Dabran Presented in: The 7^th Internation Workshop for High-Speed Networks (PfHSN 2002). bibtex Abstract: Web caching has been recognized as an important way to address three main problems in the Internet: network congestion, transmission cost and availability of web servers. As traffic increases, cache clustering becomes a natural way to increase scalability. This paper proposes an efficient scheme for increasing the cache hit-ratio in a looselycoupled cluster. In such a cluster, each proxy is able to serve every request independently of the other proxies. In order to increase the performance, the proxies may share cacheable content using some inter-cache communication protocol. The main contribution of the proposed scheme is an algorithm that increases the performance (hit-ratio) of any cache-pruning algorithm in such a cluster.
	A Unicast-based Approach for Streaming Multicast Reuven Cohen and Gideon Kaempfer Presented in: IEEE Infocom 2001. bibtex Abstract: Network layer multicast is know as the most efficient way to support multicast sessions. However, for security, QoS and other considerations, most of the real-time application protocols can be better served by upper layer (transport or application) multicast. In this paper we propose a scheme called M-RTP for multicast RTP sessions. The idea behind this scheme is to set up the multicast RTP session over a set of unicast RTP sessions, established between the various participants (source and destinations) of the multicast session. We then address the issue of finding a set of paths with maximum bottleneck for an M-RTP session. We show that this problem is NP-Complete, and propose several heuristics to solve it.
	Balanced packet Discard in ATM Networks Reuven Cohen and Yaniv Hamo Presented in: IEEE Infocom 2000 Tel-Aviv. bibtex Abstract: TCP suffers from low performance over Asynchronous Transfer Mode (ATM) networks. This is mainly because during phases of congestion, ATM drops cells without taking into account the effect this has on the upper layer protocols. Two main algorithms, called PPD and EPD, were proposed in the past for improving TCP performance. However, they address one aspect of the problem, that has only small effect on the final performance. In this paper we propose an enhanced method for packet discard, called Balanced Packet Discard (BPD), that improves TCP performance dramatically on congested networks and guarantees fairness among multiple connections. We will show that BPD increases TCP throughput by more than 25\% compared to EPD/PPD.
	Framework for Multicast in Hierarchical Networks Reuven Cohen, Roy Emek and Eyal Felstine Presented in: IEEE Infocom 2000 Tel-Aviv. bibtex Abstract: We propose a framework for the creation and maintenance of multicast trees in hierarchical ATM networks. This framework aims at coping with an inherent difficulty of topology aggregating in such networks. The main idea of the proposed framework is to distribute the tree topology information among a set of hierarchical Multicast Group Servers (MGSs) nominated for each multicast tree, while keeping regions that do not have a member in the multicast group unaware of the tree. The framework can be employed with every multicast routing algorithm designed for non-hierarchical networks.
	Crankback Prediction in Hierarchical ATM networks Eyal Felstine, Reuven Cohen and Ofer Hadar Presented in: IEEE Infocom 99 New-York. bibtex Abstract: When an ATM node discovers that it cannot continue the setup of a virtual channel under the requested Quality of Service (QoS), it initiates a backtracking procedure called "crankback." We propose a novel scheme, referred to as crankback prediction, that decreases the crankback overhead. Under the proposed scheme, nodes check during the connection admission control procedure whether the establishment of a virtual channel has a good chance to be admitted over the entire designated route. If this is not the case, crankback is initiated even before a particular QoS parameter is violated. The main idea behind the proposed scheme is to allocate a "quota" to the Peer Groups (PGs) along the message path, and then to suballocate this quota to the child PGs of these PGs. This process continues recursively until reaching the 1-level PG, which contains only physical nodes. The main advantage of the proposed scheme is that it lowers the setup delay and the processing and communication load imposed by signaling messages that establish unused portions of Virtual Channels (VCs).
	A Dynamic Approach for Efficient TCP Buffer Allocation Amit Cohen and Reuven Cohen Presented in: IC3N 98, The 7^th International Conference on Computer Communications and Networks. bibtex Abstract: The paper proposes local and global optimization schemes for eficient TCP buffSer allocation in an HTTP server. The proposed local optimization scheme dynamically adjusts the TCP send-buffer size to the connection and server characteristics. The global optimization scheme divides a certain amount of buffer space among all active TCP connections. These schemes are of increasing importance due to the large scale of TCP connection characteristics. The schemes are compared to the static allocation policy employed by a typical HTTP server, and shown to achieve considerable improvement to server performance and better utilization of its resources. The schemes require only minor code changes and only at the server.
	Schemes for Scheduling of Control Messages by Hierarchical Protocols Edi Bortnikov and Reuven Cohen Presented in: IEEE Infocom 98. bibtex Abstract: The paper addresses the problem of designing efficient scheduling policies for the transmission of control messages by hierarchical network protocols. Such protocols encounter a tradeoff between the desire to forward a control message across the tree as soon as it is received, and the desire to reduce control traffic. Scheduling problems that arise in this context are defined and discussed. The paper mainly concentrates on minimizing the average extra delay encountered by the control messages under an upper bound on the number of outgoing messages a node can send during a fixed period of time. A polynomial-time algorithm is presented for the off-line version of the problem, and then several efficient on-line heuristics are presented and compared.
	Restricted Dynamic Steiner Trees for Scalable Multicast in Datagram Networks Ehud Aharoni and Reuven Cohen Presented in: IEEE Infocom 97. bibtex Abstract: The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree.
	An Improved SSCOP-like Scheme for Avoiding Unnecessary Retransmissions and Achieving Ideal Throughput Reuven Cohen Presented in: IEEE Infocom 96. bibtex
	Handover in a Micro-Cell Packet Switched Mobile Network Reuven Cohen, B. Patel and Adrian Segall Presented in: IEEE Infocom 95. bibtex
	The Sink Tree Paradigm: Connection-less Traffic Support on ATM LANs Reuven Cohen, B. Patel, F. Schaffa and M. Willebeek-LeMair Presented in: IEEE Infocom 94. bibtex
	Smooth Intentional Rerouting and its Applications in ATM Networks Reuven Cohen Presented in: IEEE Infocom 94. bibtex
	Connection Management in ATM Networks Reuven Cohen and Adrian Segall Presented in: IEEE Infocom 94. bibtex
	Reliable Transmission of Data over an Unreliable Semi-FIFO Routing Layer Reuven Cohen and Yoram Ofek Presented in: IEEE Infocom 94. bibtex
	Multiple Logical Token-Rings in a Single High-Speed Ring Reuven Cohen and Adrian Segall Presented in: IEEE Infocom 93. bibtex
	Label Swapping With Self-Termination Reuven Cohen and Yoram Ofek Presented in: IEEE Infocom 93. bibtex
	Addressing Modes and Management Protocols in a Gigabit LAN With Switching Tables Reuven Cohen Presented in: Presented in: IEEE Proceedings of the 17^th Annual Conference on Local Computer Networks. bibtex
	Priority Mechanism Under One-Bit-Delay Constraint Reuven Cohen and Adrian Segall Presented in: Presented in: 11th Annual ACM Symposium on Principles of Distributed Computing. bibtex
	A New Scheme for Dynamic Management of Isochronous Channels in Integrated Rings Reuven Cohen and Adrian Segall Presented in: IEEE Infocom 91. bibtex
	Routes Determination in Multiple-Ring Networks Reuven Cohen and Adrian Segall Presented in: IEEE Proceedings of the 15th Annual Conference on Local Computer Networks. bibtex
	An Efficient Reliable Ring Protocol Reuven Cohen and Adrian Segall Presented in: Proc. 3rd International Workshop on Distributed Algorithms. bibtex
	Distributed Query Algorithms for High-Speed Networks Reuven Cohen and Adrian Segall Presented in: IFIP WG 6.1/WG 6.4 International Workshop on Protocols for High-Speed Networks. bibtex

	Home ♦ LCCN site ♦ CS site ♦ Technion site
Created & Designed by SITE4U

Publications

Journal Papers And Recent Conference Papers (from 2012)

Conference Papers