@@ @

# Publications

Journal Papers
Conference Papers

## Journal Papers And Recent Conference Papers (from 2012)

A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection
Reuven Cohen, Liran Katizr and Aviv Yehezkel
Accepted for oral presentation 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
Accepted to: Big Data Research journal .
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.

Inter-Datacenter Scheduling of Large Data Flows
Reuven Cohen and Gleb Polevoy
Accepted to: IEEE Transactions on Cloud Computing .
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.

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.

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
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

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
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
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
Published in: IEEE Transactions on Communications, Vol. 42, No. 2, Feb. 1994.
bibtex

An Efficient Priority Mechanism for Rings
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
Published in: Computer Networks and ISDN Systems, Volume 24 (1992), Number 2, 131-144.
bibtex

An Efficient Reliable Ring Protocol
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.

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 7th 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 7th 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
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
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 17th Annual Conference on Local Computer Networks.
bibtex

Priority Mechanism Under One-Bit-Delay Constraint
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
Presented in: IEEE Infocom 91.
bibtex

Routes Determination in Multiple-Ring Networks
Presented in: IEEE Proceedings of the 15th Annual Conference on Local Computer Networks.
bibtex

An Efficient Reliable Ring Protocol