This paper proposes the concept of a “loss-tolerant” RDMA network, instantiating as NüWa. It reveals the fundamental issues under a lossy fabric — packet losses and repetitive retransmission timeouts (RTOs) cause severe performance degradation and even service interruption. The loss-tolerant RDMA must avoid “important” packet losses that trigger RTOs. However, existing loss-protection mechanisms fail to identify these packets precisely. They either generate massive misprotection or ignore selective repeat loss recovery, resulting in buffer overflows and failures of RTO protection. To tackle these issues, NüWa thoroughly analyzes distinct loss-recovery schemes and RTO reasons for commodity NICs. It designsswitch modeandNIC modeto accurately identify and protect all important packets. The switch mode inherently supports the widely deployed non-programmable NICs, while the NIC mode offloads identification complexity to advanced programmable NICs. With effective RTO avoidance, it improves flow completion time (FCT) by 2 ∼ 10× compared to state-of-the-art (SOTA) solutions. In severe incast and large-scale networks, it reduces FCT by 100× compared with a lossless fabric. In storage applications, N¨uWa improves IOPS by ∼ 300% compared to vanilla lossy fabric. For typical AI Workloads, it accelerates AllReduce/AlltoAll communication by 5.5 ∼ 13.7× compared to SOTA lossy network solutions.

Network protocols often suffer from undetected performance degradations due to inadequate testing and a lack of efficient and accurate evaluation tools across diverse network configurations. Current methodologies face challenges like pre-modeling, oversimplifications, and focusing on limited failure modes, making them costly, impractical, or imprecise.We propose Mahak, a novel black-box framework that reconstructs the empirical performance of a given protocol throughout the multidimensional configuration space using an active learning-guided sampling strategy, without prior modeling or knowledge of the internal algorithm of the protocol. Applied to state-of-the-art Internet Congestion Control (e.g., BBR2, Sage, Orca) and Adaptive Bitrate Streaming protocols (e.g. Pensieve, BOLA, RobustMPC), Mahak explores less than 0.1% of the configuration space, and achieves up to a 12.5× reduction in mapping error compared to interpolation-based methods.By systematically identifying the complete empirical performance surface, rather than focusing on a single prominent failure, Mahak uncovers issues that would otherwise remain hidden. This end-to-end mapping equips protocol designers, QA engineers, and network operators with actionable data-driven insights across diverse metrics and configurations, supporting more reliable deployments.

Next generation applications for datacenters, such as Distributed Machine Learning (DML) and Big Data, have complex communication patterns that demand a scalable, stateless and application-aware optimal transport protocol to maximize network utilization and improve application performance. Recent transport protocols either provide limited benefits due to lack of information sharing between application and network; or implement complex stateful mechanisms to improve the application performance. In this paper, we present Omni- Transport Mechanism (Omni-TM) as a message-based congestion control protocol. Omni-TM allows exchanging message information with the network to negotiate the optimal transmission rate without maintaining a per-flow state at the switches (i.e., stateless). Omni- Tmis designed to reach maximum link capacity in one shot. Our simulation results show that Omni- Tmdemonstrates better traffic control decisions (i.e., close to zero queue length while maintaining high link utilization). Furthermore, Omni- Tmreduces Flow Completion Time (FCT) up to 45 % in a realistic workload compared to DCTCP.

In this paper, our primary objective is to showcase that the application of machine learning techniques extends beyond network protocol design. We aim to demonstrate that performance assessment of network protocols, a vital aspect of improving network infrastructures and developing better protocol designs, can be modernized through the utilization of machine learning. As a step towards this goal, we have designed and introduced Mahak, the first tool that harnesses active learning techniques to automate the performance assessment of congestion control schemes. Mahak actively learns to optimize the evaluation process of congestion control schemes so that they can generate their performance maps over a desired space without exhaustively testing them in every scenario. Mahak treats schemes under the test as black boxes. This protocol-agnostic aspect of Mahak enables users to directly assess the performance of the actual implementation of a protocol instead of their over-simplified mathematical models or simplified simulated versions.

Various congestion control protocols have been designed to achieve high performance in different network environments. Modern online learning solutions that delegate the congestion control actions to a machine cannot properly converge in the stringent time scales of data centers. We leverage multi-agent reinforcement learning to design a system for dynamic tuning of congestion control parameters at end-hosts in a data center. The system includes agents at the end-hosts to monitor and report the network and traffic states, and agents to run the reinforcement learning algorithm given the states. Based on the state of the environment, the system generates congestion control parameters that optimize network performance metrics such as throughput and latency. As a case study, we examine BBR, an example of a prominent recently-developed congestion control protocol. Our experiments demonstrate that the proposed system has the potential to mitigate the problems of static parameters.

Traffic processing on cloud-scale bandwidths has given rise to a new type of network structure, comprising a large number of highly-structured virtual entities working in close harmony. This structure, which we call a virtual sub-network, might be in need of migration, for reasons of load-balancing, maintenance, and disaster prevention. In this paper, we argue that the common migration schemes are not adequate for the complexity of this task. Therefore, we present Qanat, a migration system specifically optimized for the live migration of a virtual sub-network in its entirety to a different physical location. We show how Qanat employs widely-used techniques, such as traffic prioritization, buffering, and network tunnels, to overcome the main issues of live migration. In the paper, we categorize the main challenges of the migration task, provide an analytical study of Qanat’s algorithms, and measure its performance metrics through large-scale simulations. We conclude that Qanat can efficiently and transparently migrate virtual sub-networks and can provide a useful tool for system administrators.

Due to the dynamic nature of traffic, networks must rapidly adapt to changing conditions. This is especially true in the context of the control plane which must ensure continuous and seamless operation. Switch migration, the process of changing the controller associated with a switch, is an important tool in facilitating this goal. In this work, we study the problem of minimizing the overall time to migrate a set of switches. We examine the problem subject to constraints on controller resources and QoS groups. We show that the problem is NP-hard and provide heuristic algorithms for solving large instances in practice. Through extensive experiments, we demonstrate that the heuristics achieve performance close to optimal while reducing the running time by several orders of magnitude.

Load migration protocols have been used for load balancing in network controllers. In this poster, we argue that other network applications (e.g., power saving, network security, failure recovery, etc.) have properties that might require different load migration protocols. We introduce four new load migration protocols and show how they might match different application requirements better. We present preliminary experimental results for one of these protocols that show more than 20%-30% speedup in the total load migration time.

As network traffic and conditions change, the load on different instances of control plane changes. To ensure various control applications can operate continuously and efficiently, we need to migrate the load among controller instances. For this, we need a migration schedule that minimizes the overall migration time while ensuring the quality of service and controller resource constraints. In this poster, we show this problem is NP-hard, and show how a heuristic algorithm performs close to the best existing solution with orders of magnitude reduction in scheduling time.

Distributed control solutions were introduced to address controller reliability and scalability issues in Software-Defined Networking (SDN). The dynamic nature of network traffic can lead to load imbalance amongst controller instances. A highly loaded controller instance can be slower in responding to datapath queries, and can slow down the entire control platform as state synchronization, and consensus amongst controller instances are performed cooperatively.In this paper, we present a new and efficient load migration protocol, called ERC, for shifting input load associated with overloaded controller instances towards lightly loaded instances. Our protocol has three distinguishing properties compared to prior works on this area: it is extremely efficient, resilient to failures during migration, and ensures consistency among all controller instances. ERC can be used for a wide range of network applications including load balancing, power saving, and resource optimization. It is also significantly more efficient than existing load migration protocols with 25-55% reduction in migration time, and 10-20% reduction in required migration buffer size.

Decoupling congestion control plane from datapath can expedite the development of new congestion control solutions. It also creates opportunities for explicit rate allocation schemes. Dealing with large numbers of flows remains a major challenge. Max-min fairness – the gold standard for flow rate allocation – has a running complexity proportional to the number of flows, which might be prohibitive in large-scale networks.To accelerate explicit rate allocation, we present solutions using rate quantization, i.e. mapping the continuous range of flow rates to a small number of bins. We use Lloyd-Max, a quantization method that generates bins according to the distribution of flow rates, to dynamically adjust the quantization bins over time. Our experimental evaluation shows that the distortion caused by this quantization scheme is small, and can be negligible compared to intrinsic errors in measuring and enforcing rates in current solutions.We also show that rate quantization can significantly speed up max-min fair rate allocation, reducing the run-time by 70 − 95%. Besides, Lloyd-Max quantization using recent history of flow rates performs close to the case when we have access to the exact current (or future) rates. This is an interesting observation as it obviates the need for complex techniques that try to predict future rates.

Congestion control protocols face several challenges for achieving max-min fairness and high throughput. First, each flow has a limited view of the network state. In the absence of a centralized congestion control entity, coordination is left (directly or indirectly) to individual flow sources. Second, most flows are very volatile by nature: flow rates/demands change significantly from one instant to another.In this paper, we present a hierarchical congestion control scheme to tackle these challenges. We aggregate flows with low correlation in a hierarchical manner, and recursively compute and allocate rates to these flows. Our experiments show that correlation-aware aggregation results in significant improvements in terms of fairness (around 15% increase) and throughput (around 100% increase) compared to schemes that neglect the correlation metric. Also, we evaluate our rate allocation scheme and show that it can achieve near optimal rates for 95thpercentile of flows in most time intervals.

Decoupling congestion control plane from datapath expedites the development of new congestion control solutions and creates opportunities for explicit rate allocation schemes. However, dealing with large numbers of flows remains a major challenge. Max-min fairness - the gold standard for rate allocation - has a running complexity proportional to the number of flows, which might be prohibitive in large-scale networks. To accelerate explicit rate allocation, we suggest using rate quantization, i.e. mapping the continuous range of flow rates to a small number of bins. We use Lloyd-max, a quantization method that generates bins according to the distribution of flow rates, to dynamically adjust the quantization bins over time. Our experimental evaluation shows that the distortion caused by this quantization scheme is small, while reducing the max-min rate allocation running time by 60 − 90%.

Load migration is essential in any distributed SDN control platform due to natural load imbalance and dynamic nature of input traffic. Existing solutions focus on migrating a single switch between two controller instances. Migrating multiple switches requires careful planning due to controller resource constraints, and to ensure minimum service interruption in the network. In this poster, we present a model and a solution for migration scheduling, taking a set of switch migrations as input, generating a migration schedule with respect to controller resource and service interruption constraints.

The dynamic nature of network traffic can lead to load imbalance amongst controller instances in a distributed SDN controller. A highly loaded controller instance can be slower in responding to datapath queries, and can slow down the entire control platform. In this poster, we present a new and efficient load migration protocol for shifting input load associated with overloaded controller instances towards lightly loaded instances. Unlike existing protocols for load migration, our protocol ensures consistency among controller instances, and can handle failures during migration procedure. Our protocol reduces the migration time by 20-55%, and the migration buffer size by 10-15%.

Congestion control protocols face several challenges for achieving max-min fairness and high throughput. First, each flow has a limited view of the network state. In the absence of a centralized congestion control entity, coordination is left (directly or indirectly) to individual flows. Second, most flows are very volatile by nature: flow rates/demands change significantly from one instant to another. In this poster, we present a hierarchical congestion control scheme to tackle these challenges. We aggregate flows with low correlation in a hierarchical manner, and recursively compute and allocate rates to these flows. Our preliminary experimental results show significant promise in terms of fairness and throughput.

The trend towards simple datacenter network fabric strips most network functionality, including load balancing, out of the network core and pushes it to the edge. This slows reaction to microbursts, the main culprit of packet loss in datacenters. We investigate the opposite direction: could slightly smarter fabric significantly improve load balancing? This paper presents DRILL, a datacenter fabric for Clos networks which performs micro load balancing to distribute load as evenly as possible on microsecond timescales. DRILL employs per-packet decisions at each switch based on local queue occupancies and randomized algorithms to distribute load. Our design addresses the resulting key challenges of packet reordering and topological asymmetry. In simulations with a detailed switch hardware model and realistic workloads, DRILL outperforms recent edge-based load balancers, particularly under heavy load. Under 80% load, for example, it achieves 1.3-1.4x lower mean flow completion time than recent proposals, primarily due to shorter upstream queues. To test hardware feasibility, we implement DRILL in Verilog and estimate its area overhead to be less than 1%. Finally, we analyze DRILL's stability and throughput-efficiency.

Social media and micro-blogging platforms have been successful for communication and information exchange enjoying vast number of user participation. Given their millions of users, it is natural that there is a lot of interest for marketing and advertising on these platforms as attested by the introduced advertising platforms on Twitter and Facebook. In this paper, inspired by micro-blogging advertising platforms, we introduce two problems to aid ad and marketing campaigns. The first problem identifies topics (called analogous topics) that have approximately the same audience in a micro-blogging platform as a given query topic. The main idea is that by bidding on an analogous topic instead of the original query topic, we reach approximately the same audience while spending less of our budget. Then, we present algorithms to identify expert users on a given query topic and categorize these experts to finely understand their diversified expertise. This is imperative for word of mouth marketing where individuals have to be targeted precisely. We evaluate our algorithms and solutions for both problems on a large dataset from Twitter attesting to their eciency and accuracy compared with alternate approaches.

The trend towards simple data center network fabric strips most network functionality, including load balancing capabilities, out of the network core and pushes them to the edge. We investigate a different direction of incorporating minimal load balancing intelligence into the network fabric and show that this slightly smarter fabric significantly enhances performance. We provide a very simple in-network load balancing scheduling algorithm called DRILL which is purely local to each switch. DRILL leverages local load sensing and randomization concepts to distribute load among multiple paths. Through simulation, we show that this simple approach outperforms CONGA, a recent global edge-based load balancing scheme for data centers. We also formally prove the switch-level stability and throughput-efficiency of DRILL's scheduling algorithm.

Simplicity is a prominent advantage of Software-Defined Networking (SDN), and is often exemplified by implementing a complicated control logic as a simple control application on a centralized controller. In practice, however, SDN controllers turn into distributed systems due to performance and reliability limitations, and the supposedly simple control applications transform into complex logics that demand significant effort to design and optimize.

One of the limitations of wildcard rules in Software Defined Networks, such as OpenFlow, is losing visibility. FleXam is a flexible sampling extension for OpenFlow that allows the controller to define which packets should be sampled, what parts of each packet should be selected, and where they should be sent. Here, we present an interactive demo showing how FleXam enables the controller to dynamically adjust sampling rates and change the sampling scheme to optimally keep up with a sampling budget in the context of a traffic statistics collection application.

Speech certainly has advantages as an input modality for smartphone applications, especially in scenarios where using touch or keyboard entry is difficult, on increasingly miniaturized devices where useable keyboards are difficult to accommodate, or in scenarios where only small amounts of text need to be input, such as when entering SMS texts or responding to a CAPTCHA challenge. In this paper, we propose two new alternative ways to design CAPTCHAs in which the user says the answer instead of typing it with (a) output stimuli provided visually (SeeSay) or (b) auditorily (HearSay). Our user study results show that SeeSay CAPTCHA requires less time to be solved and users prefer it over current text-based CAPTCHA methods.

Identifying the k most influential individuals in a social network is a well-studied problem. The objective is to detect k individuals in a (social) network who will influence the maximum number of people, if they are independently convinced of adopting a new strategy (product, idea, etc). There are cases in real life, however, where we aim to instigate groups instead of individuals to trigger network diffusion. Such cases abound, e.g., billboards, TV commercials and newspaper ads are utilized extensively to boost the popularity and raise awareness.

Data available through social media and content sharing platforms present opportunities for analysis and mining. In the context of social networks, it is interesting to formalize and locate bursts of activities amongst users, related to a particular event and to report sets of socially connected users participating in such bursts. Such collections present new opportunities for understanding social events, and render new ways of online marketing.

TCP is designed to operate in a wide range of networks. Without any knowledge of the underlying network and traffic characteristics, TCP is doomed to continuously increase and decrease its congestion window size to embrace changes in network or traffic. In light of emerging popularity of centrally controlled Software-Defined Networks (SDNs), one might wonder whether we can take advantage of the global network view available at the controller to make faster and more accurate congestion control decisions. In this paper, we identify the need and the underlying requirements for a congestion control adaptation mechanism. To this end, we propose OpenTCP as a TCP adaptation framework that works in SDNs. OpenTCP allows network operators to define rules for tuning TCP as a function of network and traffic conditions. We also present a preliminary implementation of OpenTCP in a ~4000 node data center.

Among different traffic classification approaches, Deep Packet Inspection (DPI) methods are considered as the most accurate. These methods, however, have two drawbacks: (i) they are not efficient since they use complex regular expressions as protocol signatures, and (ii) they require manual intervention to generate and maintain signatures, partly due to the signature complexity. In this paper, we present CUTE, an automatic traffic classification method, which relies on sets of weighted terms as protocol signatures. The key idea behind CUTE is an observation that, given appropriate weights, the occurrence of a specific term is more important than the relative location of terms in a flow. This observation is based on experimental evaluations as well as theoretical analysis, and leads to several key advantages over previous classification techniques: (i) CUTE is extremely faster than other classification schemes since matching flows with weighed terms is significantly faster than matching regular expressions; (ii) CUTE can classify network traffic using only the first few bytes of the flows in most cases; and (iii) Unlike most existing classification techniques, CUTE can be used to classify partial (or even slightly modified) flows. Even though CUTE replaces complex regular expressions with a set of simple terms, using theoretical analysis and experimental evaluations (based on two large packet traces from tier-one ISPs), we show that its accuracy is as good as or better than existing complex classification schemes, i.e. CUTE achieves precision and recall rates of more than 90%. Additionally, CUTE can successfully classify more than half of flows that other DPI methods fail to classify.

Spam over Internet Telephony (SPIT) is a new form of spam delivered using the phone network. With the low cost of Internet telephony, SPIT has become an attractive alternative for spammers to carry out unsolicited marketing and phishing. SPIT is more intrusive than email spam as it demands immediate recipient attention. In this paper, we study characteristics of communications in a phone network with the objective of identifying “SPITters”. We collect and analyze the data from one of the largest phone providers in North America. First, we propose a new technique, Loose Tie Detection (LTD), to identify outliers based on social ties. Second, we introduce Enhanced Progressive Multi Grey-Leveling (EPMG), which identifies outliers based on call density and reciprocity. Finally, we propose SymRank, an adaptation of the PageRank algorithm that computes the reputation of subscribers based on both incoming and outgoing calls.We evaluate the three techniques and find that they compute an overlapping set of outliers. Our experiments reveal that LTD and SymRank - although seemingly independent approaches - closely match with regard to outliers, thus showing that our techniques are effective in identifying SPITters.

Verifying that a live human is interacting with an automated speech based system is needed in some applications such as biometric authentication. In this paper, we present a method to verify that the user is human. Simply stated, our method asks the user to repeat a sentence. The reply is analyzed to verify that it is the requested sentence and said by a human, not a speech synthesis system. Our method is taking advantage of both speech synthesizer and speech recognizer limitations to detect computer programs, which is new, and potentially more accessible, way to develop CAPTCHA systems. Using an acoustic model trained on voices of over 1000 users, our system can verify the user’s answer with 98% accuracy and with 80% success in distinguishing humans from computers. Index Terms: Accessibility, CAPTCHA, Speech Recognition, Speech Synthesis

Generating realistic and responsive traffic that reflects different network conditions is a challenging problem associated with performing valid experiments in network testbeds. In this work, we preset Caliper, a highly precise traffic generation tool, built on NetThreads, a flexible platform that we have created for developing packet processing applications on FPGA-based devices and the NetFPGA in particular. We will demonstrate the effect of ad-hoc inter-departure times on a commodity NIC compared to precisely timed inter-departures with Caliper. Both NetThreads and Caliper are available as free software to download.

If optical routers are to become reality, we will need several new optical technologies, one of which is to build sufficiently large optical buffers. Building optical buffers for routers is daunting: Today's electronic routers often hold millions of packets, which is well beyond the capabilities of optical technology. In this paper, we argue that two new results offer a solution. First, we show that the size of buffers in backbone routers can be made very small-just about 20 packets per linecard-at the expense of a small loss in throughput. Second, we show that integrated delay line optical buffers can store a few dozen packets on a photonic chip. With the combination of these two results, we conclude that future Internet routers could use optical buffers.

Today's online social networking (OSN) sites do little to protect the privacy of their users' social networking information. Given the highly sensitive nature of the information these sites store, it is understandable that many users feel victimized and disempowered by OSN providers' terms of service. This paper presents Lockr, a system that improves the privacy of centralized and decentralized online content sharing systems. Lockr offers three significant privacy benefits to OSN users. First, it separates social networking content from all other functionality that OSNs provide. This decoupling lets users control their own social information: they can decide which OSN provider should store it, which third parties should have access to it, or they can even choose to manage it themselves. Such flexibility better accommodates OSN users' privacy needs and preferences. Second, Lockr ensures that digitally signed social relationships needed to access social data cannot be re-used by the OSN for unintended purposes. This feature drastically reduces the value to others of social content that users entrust to OSN providers. Finally, Lockr enables message encryption using a social relationship key. This key lets two strangers with a common friend verify their relationship without exposing it to others, a common privacy threat when sharing data in a decentralized scenario.

With recent advances in optical technology, we are closer to building all-optical routers than ever before. A major problem in this area, however, is the lack of all-optical memories similar to what we have in electronics. To overcome this problem, recently, there have been several proposals that show how we can emulate First-In First-Out (FIFO) queues using a combination of fiber delay lines and switches. Unfortunately, FIFO queues cannot be used for implementing many link scheduling policies including weighted fair queuing, weighted round-robin, or strict priority, which are essential components of any modern router today. In this paper, we introduce an architecture based on fiber delay lines and optical switches that can be used for emulating Push-In First-Out (PIFO) queues. In a PIFO queue, an incoming packet can be pushed anywhere in the queue, and therefore it can be used for the implementation of various link scheduling policies. We describe a scheduling algorithm for this architecture and show that with a small speedup, we can build a PIFO queue of size N - 1 using only O(log2N) 3 × 3 optical switches. The resulting system has a minimum reliability of 99.5%, and even for the small portion of departure requests that cannot be fulfilled immediately, the requested packet is ready to depart within approximately five time slots from the request time.

It is commonly believed that the Internet has deficiencies that need to be fixed. However, making changes to the current Internet infrastructure is not easy, if possible at all. Any new protocol or design to be implemented on a global scale requires extensive experimental testing in sufficiently realistic settings; simulations alone are not enough. On the other hand, performing network experiments is intrinsically difficult for several reasons: i) Creating a network with multiple routers and a topology that is representative of a real backbone network requires significant resources, ii) Network components have proprietary architectures, which makes it almost impossible to figure out all of their internal details, iii) Making changes to network components is not always possible, iv) We cannot always use real network traces and generating high volumes of artificial traffic which closely resemble operational traffic is not trivial, and v) We need a measurement infrastructure which collects traces and measures various metrics throughout the network. These problems become even more pronounced in the context of time-sensitive network experiments. These are experiments that need very high-precision timings for packet injections into the network, or require packet-level traffic measurements with accurate timing. Experimenting with new congestion control algorithms, buffer sizing in Internet routers, and denial of service attacks which use low-rate packet injections are all examples of time-sensitive experiments, where a subtle variation in packet injection times can change the results significantly. In this work we study the challenges of conducting time-sensitive network experiments in a testbed. We provide a set of guidelines that aim at eliminating sources of inaccuracy in a time-sensitive network experiment. We should note that these guidelines are not meant to be comprehensive. For the sake of space, we only focus on issues that are most likely to be overlooked, and thus unknowingly distort the results of a time-sensitive network experiment.

During the past four years, several papers have proposed rules for sizing buffers in Internet core routers. Appenzeller et al. suggest that a link needs a buffer of size O(C/√N), where C is the capacity of the link, and N is the number of flows sharing the link. If correct, buffers could be reduced by 99% in a typical backbone router today without loss in throughput. Enachecsu et al., and Raina et al. suggest that buffers can be reduced even further to 20-50 packets if we are willing to sacrifice a fraction of link capacities, and if there is a large ratio between the speed of core and access links. If correct, this is a five orders of magnitude reduction in buffer sizes. Each proposal is based on theoretical analysis and validated using simulations. Given the potential benefits (and the risk of getting it wrong!) it is worth asking if these results hold in real operational networks. In this paper, we report buffer-sizing experiments performed on real networks - either laboratory networks with commercial routers as well as customized switching and monitoring equipment (UW Madison, Sprint ATL, and University of Toronto), or operational backbone networks (Level 3 Communications backbone network, Internet2, and Stanford). The good news: Subject to the limited scenarios we can create, the buffer sizing results appear to hold. While we are confident that the O(C/√N) will hold quite generally for backbone routers, the 20-50 packet rule should be applied with extra caution to ensure that network components satisfy the underlying assumptions.

In this paper we explore whether a general topology network built up of routers with very small buffers, can maintain high throughput under TCP's congestion control mechanism. Recent results on buffer sizing challenged the widely used assumption that routers should buffer millions of packets. These new results suggest that when smooth TCP traffic goes through a single tiny buffer of size O(log W), then close-to-peak throughput can be achieved; W is the maximum window size of TCP flows. In this work, we want to know if a network of many routers can perform well when all buffers in the network are made very small, independent of the structure of the network. This scenario represents a real network where packets go through several buffering stages on their routes. Assuming the ingress TCP traffic to a network is paced, we first prove that all routers can get by with very small buffers, if the network has a tree structure. For networks with general topology, we propose a simple active queue management policy called bounded jitter policy (BJP), and show that under the proposed policy each flow will preserve its smooth pattern across the network. Logarithmic size buffers would therefore be enough in every router of the network.

Recent theoretical results in buffer sizing research suggest that core Internet routers can achieve high link utilization, if they are capable of storing only a handful of packets. The underlying assumption is that the traffic is non-bursty, and that the system is operated below 85-90% utilization.

Abstract — Internet routers require buffers to hold packets during times of congestion. The buffers need to be fast, and so ideally they should be small enough to use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we need a bandwidth-delay product of buffering at each router so as not to lose link utilization. This can be prohibitively large. In a recent paper, Appenzeller et al. challenged this rule-of-thumb and showed that for a backbone network, the buffer size can be divided by √ N without sacrificing throughput, where N is the number of flows sharing the bottleneck. In this paper, we explore how buffers in the backbone can be significantly reduced even more, to as little as a few dozen packets, if we are willing to sacrifice a small amount of link capacity. We argue that if the TCP sources are not overly bursty, then fewer than twenty packet buffers are sufficient for high throughput. Specifically, we argue that O(log W) buffers are sufficient, where W is the window size of each flow. We support our claim with analysis and a variety of simulations. The change we need to make to TCP is minimal—each sender just needs to pace packet injections from its window. Moreover, there is some evidence that such small buffers are sufficient even if we don’t modify the TCP sources so long as the access network is much slower than the backbone, which is true today and likely to remain true in the future. We conclude that buffers can be made small enough for all-optical routers with small integrated optical buffers. I.

Energy efficiency has become increasingly critical in designing and operating wireless networks, especially for mobile ad hoc networks consisting of portable mobile wireless computing/communication devices powered by limited battery capacity. Since the energy required to transmit a given amount of data is a convex and monotonically increasing function of the transmission rate [5, 12], theoretically one can improve energy efficiency by transmitting data at lower rates. Unfortunately, low data rates result in longer transmission duration and larger communication delay at receiving end, which is usually undesirable. How to optimally schedule transmission process to both minimize the total power consumption and observe all time constraints (available times and transmission deadlines) is a challenging and interesting problem. In this paper, we propose a technique to solve the above rate scheduling problem by transforming it into finding the shortest path between two vertices of a two dimensional polygon, which yields an elegant analytical solution and easy-to-prove optimality. To the best of our knowledge, this is the first solution to the rate scheduling problem in its general form. 1.

Abstract — Routing in mobile ad-hoc networks is hard because the topology can change very rapidly. By the time new paths are discovered, the network can change again – and in extreme cases, packets circulate endlessly and the system is unstable. Most attempts to solve this problem have required that the topology changes slowly. In this paper, we propose a routing algorithm called Volcano Routing Scheme (VRS) which will route packets successfully, even if the topology changes very rapidly. VRS doesn’t need to discover routes, or exchange routing information; it simply balances the load locally between adjacent pairs of nodes. We show that under some loose conditions on network topology changes, VRS keeps the system stable. Simulations also suggest that VRS is stable for various models of mobility, different communication patterns, and different amounts of flow in the network. Interestingly, we prove that when the network topology is static, packets follow the shortest path. I.

Input Queued (IQ) switches have been well studied in the past two decades by researchers. The main problem concerning IQ switches is scheduling the switching fabric in order to transfer packets from input ports to output ports. Scheduling is relatively easier when all packets are of the same size. However, in practice, packets are of variable length. In the current implementation of switches, variable length packets are segmented into fixed length packets-also knowns as cells-for the purpose of scheduling. However, such cell-based switching comes with some significant disadvantages: (a) loss of bandwidth due to the existence of incomplete cells; and (b) additional overhead of segmentation of packets and re-assembly of cells. This is a strong motivation to study packet-based scheduling, i.e., scheduling the transfer of packets without segmenting them. The problem of packet scheduling was first considered by Marsan et al. They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this paper, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan et al. are strongly dependent on the arrival distribution. Next, we propose a new class of "waiting" algorithms. We show that the "waiting"-MWM algorithm is stable for any admissible traffic using the fluid limit technique. We would like to note that the algorithms presented in this paper are distribution independent or universal. The algorithms and proof methods of this paper may be useful in the context of other scheduling problems.

Multi-path routing has been studied thoroughly in the context of wired networks. Ii has been shown that using multiple paths to route messages between any source-destination pair of nodes (instead of using a single path) balances the load more evenly throughout the network. The common belief is that the same is true for ad hoc networks, i.e., multi-path routing balances the load significantly better than single-path routing. We show that this is not necessarily the case. We introduce a new model for evaluating the load balance under multi-path routing, when the paths chosen are the first K shortest paths (for a pre-specified K). Using this model, we show that unless we use a very large number of paths (which is very costly and therefore infeasible) the load distribution is almost the same as single shortest path routing. This is in contrary to the previous existing results which assume that multi-path routing distributes the load uniformly.

Input Queued (IQ) switches have been very well studied in the recent past. The main problem in the IQ switches concerns scheduling. The main focus of the research has been the fixed length packet-known as cells-case. The scheduling decision becomes relatively easier for cells compared to the variable length packet case as scheduling needs to be done at a regular interval of fixed cell time. In real traffic dividing the variable packets into cells at the input side of the switch and then reassembling these cells into packets on the output side achieve it. The disadvantages of this cell-based approach are the following: (a) bandwidth is lost as division of a packet may generate incomplete cells, and (b) additional overhead of segmentation and reassembling cells into packets. This motivates the packet scheduling: scheduling is done in units of arriving packet sizes and in nonpreemptive fashion. In M.A. Marsan et al. (2001) the problem of packet scheduling was first considered. They show that under any admissible Bernoulli i.i.d. arrival traffic a simple modification of maximum weight matching (MWM) algorithm is stable, similar to cell-based MWM. In this paper, we study the stability properties of packet based scheduling algorithm for general admissible arrival traffic pattern. We first show that the result of Marsan et al. extends to general regenerative traffic model instead of just admissible traffic, that is, packet based MWM is stable. Next we show that there exists an admissible traffic pattern under which any work-conserving (that is maximal type) scheduling algorithm will be unstable. This suggests that the packet based MWM will be unstable too. To overcome this difficulty we propose a new class of "waiting" algorithms. We show that "waiting"-MWM algorithm is stable for any admissible traffic using fluid limit technique.