In-network computing via smart networking devices is a recent trend in modern datacenter networks. State-of-the-art switches with near line-rate computing and aggregation capabilities enable acceleration and improved resource utilization for modern applications like large-scale distributed and federated machine learning, as well as big data analytics. We study the problem of activating a limited number of in-network computing devices within a network, aiming at reducing the overall cost incurred by such a deployment. Such limitations on the number of in-network computing elements arise, e.g., in incremental upgrades of network infrastructure, and are also due to requiring specialized middleboxes, or FPGAs, for supporting heterogeneous workloads, and multiple tenants. We present an efficient optimal algorithm for placing such devices in tree networks with arbitrary link rates, and further evaluate its performance in various scenarios and for various tasks, including federated/distributed ML and big data analytics. Our results show that even a small fraction of network devices supporting in-network aggregation leads to a significant reduction in network utilization cost. Furthermore, we show that various intuitive strategies for performing such placements are significantly inferior compared with our solution, for varying workloads, tasks, and link rates.

We consider a new locality pattern in the form of burstiness to improve cache effectiveness in workflows where items are requested in possibly infrequent yet costly batches. Adding a cache that handles only bursty items to existing State-Of-The-Art algorithms shows a significant improvement in overall average time per query.

Deploying services efficiently while satisfying their quality requirements is a major challenge in network slicing. Effective solutions place instances of the services' virtual network functions (VNFs) at different locations of the cellular infrastructure and manage such instances by scaling them as needed. In this work, we address the above problem and the very relevant aspect of sub-slice reuse among different services. Further, unlike prior art, we account for the services' finite lifetime and time-varying traffic load. We identify two major sources of inefficiency in service management: (i) the overspending of computing resources due to traffic of multiple services with different latency requirements being processed by the same virtual machine (VM), and (ii) the poor packing of traffic processing requests in the same VM, leading to opening more VMs than necessary. To cope with the above issues, we devise an algorithm, called REShare, that can dynamically adapt to the system's operational conditions and find an optimal trade-off between the aforementioned opposite requirements. We prove that REShare has low algorithmic complexity and is asymptotic 2-competitive under a non-decreasing load. Numerical results, leveraging real-world scenarios, show that our solution outperforms alternatives, swiftly adapting to time-varying conditions and reducing service cost by over 25%.

Placement of VMs in the cloud is one of the most fundamental problems in systems research. Traditionally, placement algorithms assume that the schedulers have complete information about the currently available resources at each host. However, this assumption is in many cases unrealistic, as gathering fresh status information from each of the thousands of hosts in a large data center incurs excessive communication overhead, which results in long queueing delays. Efforts to resolve this problem by employing several parallel schedulers typically exhibit collisions when several schedulers are simultaneously trying to place VMs on the same host. Our work analyzes the performance of various placement algorithms and provides empirical evidence that using multiple randomized schedulers obtains high throughput, while significantly decreasing both the communication overhead, and the number of collisions between schedulers. We, therefore, introduce Adaptive Partial State Random (APSR) – an efficient parallel random resource management algorithm that samples only from a small number of hosts and dynamically adjusts the degree of parallelism to provide provable guarantees on the probability of collisions between distinct schedulers. We formally analyze APSR, evaluate it on real workloads, and integrate it into the popular OpenStack cloud management platform. Our evaluation shows that APSR matches the throughput provided by other parallel schedulers, while achieving up to 13x lower decline ratio and a reduction of over 85% in communication overheads.

We consider a hierarchical edge-cloud architecture in which services are provided to mobile users as chains of virtual network functions. Each service has specific computation requirements and target delay performance, which require placing the corresponding chain properly and allocating a suitable amount of computing resources. Furthermore, chain migration may be necessary to meet the services’ target delay. We model and formalize the problem of finding a feasible chain placement and resource allocation, while minimizing the migration, bandwidth, and computation costs. We tackle this problem by partitioning it into a (i) CPU allocation problem, and a (ii) placement problem. For the CPU allocation problem, we find an optimal solution. For the placement problem, we show that even finding a feasible solution is NP-hard, and envision an algorithm that is guaranteed to find a feasible solution while leveraging a bounded amount of resource augmentation. Our algorithms are incorporated into a solution framework that aims to minimize both the cost and the required resource augmentation. The results, obtained through trace-driven, large-scale simulations, show that our framework can provide a close-to-optimal solution while running several orders of magnitude faster than an ILP solver.

Distributed computing has become a common practice nowadays, where recent focus has been given to the usage of smart networking devices with in-network computing capabilities. State-of-the-art switches with near-line rate computing and aggregation capabilities enable acceleration and improved performance for various modern applications like big data analytics and large-scale distributed and federated machine learning.In this work, we formulate and study the theoretical algorithmic foundations of such approaches, and focus on how to deploy and use constrained in-network computing capabilities within the data center. We focus our attention on reducing the network congestion, i.e., the most congested link in the network, while supporting the given workload(s). We present an efficient optimal algorithm for tree-like network topologies and show that our solution provides as much as an x13 improvement over common alternative approaches. In particular, our results show that having merely a small fraction of network devices that support in-network aggregation can significantly reduce the network congestion, both for single and multiple workloads.

Distributed caching systems such as content distribution networks often advertise their content via lightweight approximate indicators (e.g., Bloom filters) to efficiently inform clients where each datum is likely cached. While false-positive indications are necessary and well understood, most existing works assume no false-negative indications. Our work illustrates practical scenarios where false-negatives are unavoidable and ignoring them significantly impacts system performance. Specifically, we focus on false-negatives induced by indicator staleness, which arises whenever the system advertises the indicator only periodically, rather than immediately reporting every change in the cache. Such scenarios naturally occur, e.g., in bandwidth-constraint environments or when latency impedes each client’s ability to obtain an updated indicator. Our work introduces novel false-negative aware access policies that continuously estimate the false-negative ratio and sometimes access caches despite negative indications. We present optimal policies for homogeneous settings and provide approximation guarantees for our algorithms in heterogeneous environments. We further perform an extensive simulation study with multiple real system traces. We show that our false-negative aware algorithms incur a significantly lower service cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).

In-network computing via smart networking devices is a recent trend for modern datacenter networks. State-of-the-art switches with near line rate computing and aggregation capabilities are developed to enable, e.g., acceleration and better utilization for modern applications like big data analytics, and large scale distributed and federated machine learning. We formulate and study the problem of activating a limited number of in-network computing devices within a network, aiming at reducing the overall network utilization for a given workload. Such limitations on the number of in-network computing elements per workload arise, e.g., in incremental upgrades of network infrastructure, and are also due to requiring specialized middleboxes, or FPGAs, that should support heterogeneous workloads, and multiple tenants.

Distributed caching systems such as content distribution networks often advertise their content via lightweight approximate indicators (e.g., Bloom filters) to efficiently inform clients where each datum is likely cached. While false-positive indications are necessary and well understood, most existing works assume no false-negative indications. Our work illustrates practical scenarios where false-negatives are unavoidable and ignoring them has a significant impact on system performance. Specifically, we focus on false-negatives induced by indicator staleness, which arises whenever the system advertises the indicator only periodically, rather than immediately reporting every change in the cache. Such scenarios naturally occur, e.g., in bandwidth-constraint environments or when latency impedes each client's ability to obtain an updated indicator. Our work introduces novel false-negative aware access policies that continuously estimate the false-negative ratio and sometimes access caches despite negative indications. We present optimal policies for homogeneous settings and provide approximation guarantees for our algorithms in heterogeneous environments. We further perform an extensive simulation study with multiple real system traces. We show that our false-negative aware algorithms incur a significantly lower access cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).

Cache advertisements reduce the access cost by allowing users to skip the cache when it does not contain their datum. Such advertisements are used in multiple networked domains such as 5G networks, wide area networks, and information-centric networking. The selection of an advertisement strategy exposes a trade-off between the access cost and bandwidth consumption. Still, existing works mostly apply a trial-and-error approach for selecting the best strategy, as the rigorous foundations required for optimizing such decisions is lacking.Our work shows that the desired advertisement policy depends on numerous parameters such as the cache policy, the workload, the cache size, and the available bandwidth. In particular, we show that there is no ideal single configuration. Therefore, we design an adaptive, self-adjusting algorithm that periodically selects an advertisement policy. Our algorithm does not require any prior information about the cache policy, cache size, or work-load, and does not require any apriori configuration. Through extensive simulations, using several state-of-the-art cache policies, and real workloads, we show that our approach attains a similar cost to that of the best static configuration (which is only identified in retrospect) in each case.

Network Function Virtualization (NFV) carries the potential for on-demand deployment of network algorithms in virtual machines (VMs). In large clouds, however, VM resource allocation incurs delays that hinder the dynamic scaling of such NFV deployment. Parallel resource management is a promising direction for boosting performance, but it may significantly increase the communication overhead and the decline ratio of deployment attempts. Our work analyzes the performance of various placement algorithms and provides empirical evidence that state of the art parallel resource management dramatically increases the decline ratio of deterministic algorithms, but hardly affects randomized algorithms. We therefore introduce APSR - an efficient parallel random resource management algorithm that requires information only from a small number of hosts and dynamically adjusts the degree of parallelism to provide provable decline ratio guarantees. We formally analyze APSR, evaluate it on real workloads, and integrate it into the popular OpenStack cloud management platform. Our evaluation shows that APSR matches the throughput provided by other parallel schedulers, while achieving up to 13x lower decline ratio and a reduction of over 85% in communication overheads.

Having multiple data stores that can potentially serve content is common in modern networked applications. Data stores often publish approximate summaries of their content to enable effective utilization. Since these summaries are not entirely accurate, forming an efficient access strategy to multiple data stores becomes a complex risk management problem. This paper formally models this problem as a cost minimization problem, while taking into account both access costs, the inaccuracy of the approximate summaries, as well as the penalties incurred by failed requests. We introduce practical algorithms with guaranteed approximation ratios and further show that they are optimal in various settings. We also perform an extensive simulation study based on real data and show that our algorithms are more robust than existing heuristics. That is, they exhibit near-optimal performance in various settings, whereas the efficiency of existing approaches depends upon system parameters that may change over time, or be otherwise unknown.

Having multiple data stores that can potentially serve content is common in modern networked applications. Data stores often publish approximate summaries of their content to enable effective utilization. Since these summaries are not entirely accurate, forming an efficient access strategy to multiple data stores becomes a complex risk management problem.This paper formally models this problem, and introduces practical algorithms with guaranteed approximation ratios, and in particular we show that our algorithms are optimal in a variety of settings. We also perform an extensive simulation study based on real data, and show that our algorithms are more robust than existing heuristics. That is, they exhibit near optimal performance in various settings whereas the efficiency of existing approaches depends upon system parameters that may change over time, or be otherwise unknown.

Thanks to its computational and forwarding capabilities, the mobile network infrastructure can support several third-party (“vertical”) services, each composed of a graph of virtual (network) functions (VNFs). Importantly, one or more VNFs are often common to multiple services, thus the services deployment cost could be reduced by letting the services share the same VNF instance instead of devoting a separate instance to each service. By doing that, however, it is critical that the target KPI (key performance indicators) of all services are met. To this end, we study theVNF sharingproblem and make decisions on 1) when sharing VNFs among multiple services is possible, 2) how to adapt the virtual machines running the shared VNFs to the combined load of the assigned services, and 3) how to prioritize the services traffic within shared VNFs. All decisions aim to minimize the cost for the mobile operator, subject to requirements on end-to-end service performance, e.g., total delay. Notably, we show that the aforementioned priorities should be managed dynamically and vary across VNFs. We then propose the FlexShare algorithm to provide near-optimal VNF-sharing and priority assignment decisions in polynomial time. We prove that FlexShare is within a constant factor from the optimum and, using real-world VNF graphs, we show that it consistently outperforms baseline solutions.

Recent advances in the standardization of 4G cellular networks introduce the notion of multi-coverage, where multiple base stations may collaboratively satisfy the demands of mobile users. We provide a theoretical model for studying such multi-coverage environments, in highly heterogeneous settings, where users demands and profits may vary, as can base stations' capacities and the rates with which they can service the users. Whereas previous works provided solutions that were only applicable to scenarios where rates are uniform throughout the network, or allowed a mobile user to be serviced by at most one base station, we present several algorithms for the multi-coverage problem in the presence of non-uniform rates, and analyze their performance. We complete our study by a simulation study that further validates our results and provides further insight into algorithm design, depending on the users' characteristics.

Passive monitoring utilizing distributed wireless sniffers is an effective technique to monitor activities in wireless infrastructure networks for fault diagnosis, resource management, and critical path analysis. In this paper, we introduce a quality of monitoring (QoM) metric defined by the expected number of active users monitored, and investigate the problem of maximizing QoM by judiciously assigning sniffers to channels based on the knowledge of user activities in a multichannel wireless network. Two types of capture models are considered. The user-centric model assumes the frame-level capturing capability of sniffers such that the activities of different users can be distinguished while the sniffer-centric model only utilizes the binary channel information (active or not) at a sniffer. For the user-centric model, we show that the implied optimization problem is NP-hard, but a constant approximation ratio can be attained via polynomial complexity algorithms. For the sniffer-centric model, we devise stochastic inference schemes to transform the problem into the user-centric domain, where we are able to apply our polynomial approximation algorithms. The effectiveness of our proposed schemes and algorithms is further evaluated using both synthetic data as well as real-world traces from an operational WLAN.

Cell selection is the process of determining the cell(s) that provide service to each mobile station. Optimizing these processes is an important step toward maximizing the utilization of current and future cellular networks. We study the potential benefit of global cell selection versus the current local mobile SNR-based decision protocol. In particular, we study the new possibility available in OFDMA-based systems, such as IEEE 802.16m and LTE-Advanced, of satisfying the minimal demand of a mobile station simultaneously by more than one base station. We formalize the problem as an optimization problem, and show that in the general case this problem is not only NP-hard but also cannot be approximated within any reasonable factor. In contrast, under the very practical assumption that the maximum required bandwidth of a single mobile station is at most an r-fraction of the capacity of a base station, we present two different algorithms for cell selection. The first algorithm produces a (1-r)-approximate solution, where a mobile station can be covered simultaneously by more than one base station. The second algorithm produces a 1-r/2-r-approximate solution, while every mobile station is covered by at most one base station. We complete our study by an extensive simulation study demonstrating the benefits of using our algorithms in high-loaded capacity-constrained future 4G networks, compared to currently used methods. Specifically, our algorithms obtain up to 20 percent better usage of the network's capacity, in comparison with the current cell selection algorithms.

In many applications, the traffic traversing the network has interpacket dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such interpacket dependencies, and design algorithms for performing packet discard. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of interdependent packets. We provide two guidelines for designing buffer management algorithms, and demonstrate their effectiveness. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also perform a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best known offline algorithm.

Current network processors (NPs) increasingly deal with packets with heterogeneous processing times. In such an environment, packets that require many processing cycles delay low-latency traffic because the common approach in today's NPs is to employ run-to-completion processing. These difficulties have led to the emergence of the Multipass NP architecture, where after a processing cycle ends, all processed packets are recycled into the buffer and recompete for processing resources. In this paper, we provide a model that captures many of the characteristics of this architecture, and we consider several scheduling and buffer management algorithms that are specially designed to optimize the performance of multipass network processors. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study, which validates our results.

Current network processors (NPs) increasingly deal with packets with heterogeneous processing times. As a consequence, packets that require many processing cycles can significantly delay low-latency traffic, because the common approach in today's NPs is to employ run-to-completion processing. These difficulties have led to the emergence of the Multipass NP architecture, where after a processing cycle ends, all processed packets are recycled into the buffer and re-compete for processing resources. In this work we provide a model that captures many of the characteristics of this architecture, and consider several scheduling and buffer management algorithms that are specially designed to optimize the performance of multipass network processors. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study that validates our results.

We consider packet networks with limited buffer space at the nodes, and are interested in the question of maximizing the number of packets that arrive to destination rather than being dropped due to full buffers. We initiate a more refined analysis of the throughput competitive ratio of admission and scheduling policies in the Competitive Network Throughput model [Aiello et al. 2005], taking into account not only the network size but also the buffer size and the injection rate of the traffic. We specifically consider the problem of information gathering on the line, with limited buffer space, under adversarial traffic. We examine how the buffer size and the injection rate of the traffic affect the performance of the greedy protocol for this problem. We establish upper bounds on the competitive ratio of the greedy protocol in terms of the network size, the buffer size, and the adversary's rate, and present lower bounds which are tight up to constant factors. These results show, for example, that provisioning the network with sufficiently large buffers may substantially improve the performance of the greedy protocol in some cases, whereas for some high-rate adversaries, using larger buffers does not have any effect on the competitive ratio of the protocol.

In many applications the traffic traversing the network has inter-packet dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such inter-packet dependencies, and design algorithms for performing packet discards. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of inter-dependent packets. We provide two guidelines for designing buffer management algorithms for this problem, and demonstrate the effectiveness of these criteria. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also present a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best offline algorithm.

Passive monitoring utilizing distributed wireless sniffers is an effective technique to monitor activities in wireless infrastructure networks for fault diagnosis, resource management and critical path analysis. In this paper, we introduce a quality of monitoring (QoM) metric defined by the expected number of active users monitored, and investigate the problem of maximizing QoM by judiciously assigning sniffers to channels based on knowledge of user activities in a multi-channel wireless network. Two capture models are considered. The first one, called the user-centric model assumes frame-level capturing capability of sniffers such that the activities of different users can be distinguished. The second one, called the sniffer-centric model only utilizes binary channel information (active or not) at a sniffer. For the user-centric model, we show that the implied optimization problem is NP-hard, but a constant approximation ratio can be attained via polynomial complexity algorithms. For the sniffer-centric model, we devise a stochastic inference scheme that transforms the problem into the user-centric domain, where we are able to apply our polynomial approximation algorithms. The effectiveness of our proposed scheme and algorithms is further evaluated using both synthetic data as well as real-world traces from an operational WLAN.

We consider a multipacket reception channel shared by several communication applications. This is the case, for example, in a single radio mesh network where neighboring cells use the same radio channel. In such scenarios, unlike the common multiple access model, several transmissions may succeed simultaneously, depending on the actual locations of the sending and receiving stations, and thus channel utilization may be greater than 1. Our goal is to derive a decentralized access control mechanism that maximizes the channel utilization, while taking into account fairness among the different users. We focus on a simple case where each user can adjust a single parameter that determines its transmission probability in any time slot, and develop such a protocol for the general problem, where users are distributed arbitrarily, based on strong motivation which is derived from analytical bounds for homogeneous interferences. We further show, using extensive simulations, that this protocol achieves a high utilization of radio resources compared to any other protocol (not necessarily based on a simple parameter), while maintaining fairness between all users.

We introduce the problem of managing a FIFO buffer of bounded space, where arriving packets have dependencies among them. Our model is motivated by the scenario where large data frames must be split into multiple packets, because maximum packet size is limited by data-link restrictions. A frame is considered useful only if sufficiently many of its constituent packets are delivered. The buffer management algorithm decides, in case of overflow, which packets to discard and which to keep in the buffer. The goal of the buffer management algorithm is to maximize throughput of useful frames. This problem has a variety of applications, e.g., Internet video streaming, where video frames are segmented and encapsulated in IP packets sent over the Internet. We study the complexity of the above problem in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis.

For widely used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of the traffic is typically captured by its delay jitter , that is, the difference between the maximal and minimal end-to-end delays. The task of minimizing the jitter is done by jitter regulators that use a limited-size buffer in order to shape the traffic. In many real-life situations regulators must handle multiple streams simultaneously and provide low jitter on each of them separately. Moreover, communication links have limited capacity, and these may pose further restrictions on the choices made by the regulator. This article investigates the problem of minimizing jitter in such an environment, using a fixed-size buffer. We show that the offline version of the problem can be solved in polynomial time, by introducing an efficient offline algorithm that finds a release schedule with optimal jitter. When regulating M streams in the online setting, we take a competitive analysis point of view and note that, in the upcapacitated case, previous results in Mansour and Patt-Shamir [2001] can be extended to an online algorithm that uses a buffer of size 2⋅ M ⋅ B and obtains the optimal jitter possible with a buffer of size B (and an offline algorithm). The question arises whether such a resource augmentation is essential. We answer this question in the affirmative, by proving a lower bound that is tight up to a factor of 2, thus showing that jitter regulation does not scale well as the number of streams increases unless the buffer is sized-up proportionally.

We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2, O (log n )) bicriteria approximation, that is, the solution's profit is at least a fraction of 1/ O (log n ) of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any ε ∈ (0,1], guarantees a (1 + ϵ, O (1/ε log n ))-approximation.

We consider an abstraction of the problem of managing buffers where traffic is subject to service level agreements (SLA). In our abstraction of SLAs, some packets are marked as ldquocommittedrdquo and the others are marked as ldquoexcess.rdquo The service provider must on one hand deliver all committed packets, and on the other hand can get extra revenue for any excess packet delivered. We study online algorithms managing a buffer with limited space, whose task is to decide which packets should be delivered and which should be dropped. Using competitive analysis, we show how to utilize additional buffer space and link bandwidth so that the number of excess packets delivered is comparable to the best possible by any off-line algorithm, while guaranteeing that no arriving committed packet is ever dropped. Simulations of such traffic (alone and combined with additional best-effort traffic) show that the performance of our algorithm is in fact much better than our analytical guarantees.

Cell selection is the process of determining the cells that provide service to each mobile station. Optimizing these processes is an important step towards maximizing the utilization of current and future cellular networks. In this paper we study the potential benefit of global cell selection versus the current local mobile SNR-based decision protocol. In particular, we study the new possibility that is feasible in OFDMA-based systems, of satisfying the minimal demand of a mobile station simultaneously by more than one base station. We formalize the problem as an optimization problem, called the all-or-nothing demand maximization problem, and show that when the demand of a single mobile station can exceed the capacity of a base station, this problem is not only NP-hard but also cannot be approximated within any reasonable factor. In contrast, under the very practical assumption that the maximum required bandwidth of a single mobile station is at most an r-fraction of the capacity of a base station, we present two different algorithms for cell selection. The first algorithm guarantees a satisfaction of at least a 1- r r fraction of an optimal assignment, where a mobile station can be covered simultaneously by more than one base station. The second algorithm guarantees a satisfaction of at least a 1-r/1-r fraction of an optimal assignment, while every mobile station is covered by at most one base station. Using an extensive simulation study we show that the cell selections determined by our algorithms achieve a better utilization of high-loaded capacity-constrained future 4G networks than the current SNR- based scheme. Specifically, our algorithms are shown to obtain up to 20% better usage of the network's capacity, in comparison with the current cell selection algorithms.

We consider packet networks with limited buffer space at the nodes, and are interested in the question of maximizing the number of packets that arrive to destination rather than being dropped due to full buffers.We initiate a more refined analysis of the throughput competitive ratio of admission and scheduling policies in the Competitive Network Throughput model [2], taking into account not only the network size but also the buffer size and the injection rate of the traffic.We specifically consider the problem of information gathering on the line, with limited buffer space, under adversarial traffic. We examine how the buffer size and the injection rate of the traffic affect the performance of the greedy protocol for this problem. We establish upper bounds on the competitive ratio of the greedy protocol in terms of the network size, the buffer size, and the adversary's rate, and present lower bounds which are tight up to constant factors. These results show, for example, that provisioning the network with sufficiently large buffers may substantially improve the performance of the greedy protocol in some cases, whereas for some high-rate adversaries, using larger buffers does not have any effect on the competitive ratio of the protocol.

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002). In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first deterministic online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios. We complete our study with several experimental results.