On the Admission of Dependent Flows in Powerful Sensor Networks PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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 PDF Publication 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:IEEE Proceedings of the 17th Annual Conference on Local Computer Networks. bibtex
Priority Mechanism Under One-Bit-Delay Constraint Reuven Cohen and Adrian Segall
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