Internet traffic measurements have shown that the majority of the Internet's flows are short, while a small percentage of the largest flows are responsible for most of the bytes. To exploit this property for performance improvement in routers and Web servers, several studies have proposed size-based schedulings to offer preferential treatment to the shortest flows. In this work, we present analytical and simulation results which confirm that size-based scheduling will ease the task of launching DDOS attacks on the Internet.

We analyze routing algorithm for wireless sensor networks called power aware differentiated routing (PADR), which is proposed for collaborative routing of real-time (RT) and non-real time (NRT) traffic in a sensor field in order to prolong the otherwise shorter life time of RT sensor network. PADR uses nodes in the non-real time network as backup for routing RT traffic. It involves swapping a forwarding node for RT traffic from a node with critical minimum power level to the node with the best power level (often from a node in RT network to a node in NRT network). We derive analytical expressions for life time of RT and NRT networks under PADR routing protocol. The numerical results show that the performance of PADR depends on the remaining power of sensor nodes during route swapping. The results also show that PADR can increase the life time of RT network by up to 50%, and that similar reduction level of life time is incurred to NRT network.

We propose several models based on discrete-time Markov chains for the analysis of distributed hash tables (DHTs). Specifically, we examine the Pastry routing protocol, as well as a Stealth DHT adaptation of Pastry to compute their exact expressions for average number of lookup hops. We show that our analytical models match with the protocols' simulation results almost perfectly, making them ideal for rapid evaluation.

Most Distributed Hash Tables (DHTs) simply consider interconnecting homogeneous nodes on the same overlay. However, realistically nodes on a network are heterogeneous in terms of their capabilities. Because of this, traditional DHTs have been shown to exhibit poor performance in a real-world environment. Additionally, we believe that it is this approach that contributes to a limited exploitation of peer-to-peer technologies. Previous work on super-peers in DHTs was proposed to address these performance issues, however the strategy used is often based on locally clustering peers around individual super-peers. This method of super-peering, however, compromises fundamental features such as load-balancing, resilience and routing efficiency, which traditional DHTs originally promised to offer.

peer reviewed

The Least Attained Service (LAS) scheduling policy, when used for scheduling packets over the bottleneck link of an Internet path, can greatly reduce the average flow time for short flows while not significantly increasing the average flow time for the long flows that share the same bottleneck. No modification of the packet headers is required to implement the simple LAS policy. However, previous work has also shown that a drawback of the LAS scheduler is that, when link utilization is greater than 70%, long flows experience large jitter in their packet transfer times as compared to the conventional First-Come-First-Serve (FCFS) link scheduling. This paper proposes and evaluates new differentiated LAS scheduling policies that reduce the jitter for long flows that are identified as "priority" flows.To evaluate the new policies, we develop analytic models to estimate average flow transfer time as a function of flow size, and average packet transmission time as a function of position in the flow, for the single-bottleneck "dumbbell topology" used in many ns simulation studies. Models are developed for FCFS scheduling, LAS scheduling, and each of the new differentiated LAS scheduling policies at the bottleneck link. Over a wide range of configu-rations, the analytic estimates agree very closely with the ns estimates. Thus, the analytic models can be used instead of simulation for comparing the policies with respect to mean flow transfer time (as a function of flow size) and mean packet transfer time. Furthermore, an initial discrepancy between the analytic and simulation estimates revealed errors in the parameter values that are often specified in the widely used ns Web workload generator. We develop an improved Web workload specification, which is used to estimate the packet jitter for long flows (more accurately than with previous simulation workloads).Results for the scheduling policies show that a particular policy, LAS-log, greatly improves the mean flow transfer time for priority long flows while providing performance similar to LAS for the ordinary flows. Simulations show that the LAS-log policy also greatly reduces the jitter in packet delivery times for the priority flows.

Recent studies of Internet traffic have shown that flow size distributions often exhibit a high variability property in the sense that most of the flows are short and more than half of the total load is constituted by a small percentage of the largest flows. In the light of this observation, it is interesting to revisit scheduling policies that are known to favor small jobs in order to quantify the benefit for small and the penalty for large jobs. Among all scheduling policies that do not require knowledge of job size, the least attained service (LAS) scheduling policy is known to favor small jobs the most. We investigate the M/G/1/LAS queue for both, load ? < 1 and ? = 1. Our analysis shows that for job size distributions with a high variability property, LAS favors short jobs with a negligible penalty to the few largest jobs, and that LAS achieves a mean response time over all jobs that is close to the mean response time achieved by SRPT.Finally, we implement LAS in the ns-2 network simulator to study its performance benefits for TCP flows. When LAS is used to schedule packets over the bottleneck link, more than 99% of the shortest flows experience smaller mean response times under LAS than under FIFO and only the largest jobs observe a negligible increase in response time. The benefit of using LAS as compared to FIFO is most pronounced at high load.

This paper concentrates on obtaining uniform weighted round robin schedules for input queued packet switches. The desired schedules are uniform in the sense that each connection is serviced at regularly spaced time slots, where the spacing is proportional to the inverse of the guaranteed data rate. Suitable applications include ATM networks as well as satellite switched TDMA systems that provide per packet delay guarantees. Three heuristic algorithms are proposed to obtain such schedules under the constraints imposed by the unit speedup of input queued switches. Numerical experiments indicate that the algorithms have remarkable performance in finding uniform schedules.