Proceedings - IEEE INFOCOM

This work develops a discrete time feedback system model for a simplified TCP (transmission control protocol) network with RED (random early detection) control. The model involves sampling the buffer occupancy variable at certain instants. The dynamical model is used to analyze the TCP-RED operating point and its stability with respect to various RED controller and system parameters. Bifurcations are shown to occur as various system parameters are varied. These bifurcations, which involve the emergence of oscillatory and/or chaotic behavior, may provide an explanation for the parameter sensitivity observed in practice. The bifurcations arise due to the presence of a nonlinearity in the characteristics of TCP throughput as a function of drop probability at the gateway. Among the bifurcations observed in the system are the period-doubling bifurcation and border collision bifurcations. The bifurcations are studied analytically, numerically, and experimentally.

Chúng tôi nghiên cứu về việc lập lộ trình và phân bổ bước sóng cho mạng quang WDM định tuyến theo bước sóng (WR) với phân chia thời gian (TDM) được chuyển mạch mạch. Trong một mạng WR thông thường, toàn bộ bước sóng được chỉ định cho một phiên (hoặc mạch) nhất định. Điều này có thể dẫn đến việc sử dụng kênh thấp hơn khi các phiên giao dịch riêng lẻ không cần toàn bộ băng thông kênh. Chúng tôi xem xét một cách tiếp cận dựa trên TDM để giảm thiểu sự không hiệu quả này. Trong kiến trúc này, mỗi bước sóng được phân chia theo miền thời gian thành các khe thời gian có độ dài cố định được tổ chức như một khung TDM. Nhiều phiên được phân chia trên mỗi bước sóng bằng cách chỉ định một tập con của các khe TDM cho mỗi phiên. Do đó, với yêu cầu phiên có băng thông đã chỉ định, mục tiêu là xác định lộ trình, phân bổ bước sóng và phân bổ khe thời gian (RWTA) đáp ứng yêu cầu. Điều này tương tự như việc lập lộ trình và phân bổ bước sóng trong các mạng WR. Chúng tôi trình bày một tập hợp các thuật toán RWTA và nghiên cứu hiệu suất chặn. Chúng tôi sử dụng thuật toán lập lộ trình theo đường ngắn nhất hiện có với một hàm chi phí liên kết mới, hàm trọng số ít kháng cự (LRW), nó tích hợp thông tin sử dụng bước sóng. Chúng tôi sử dụng lựa chọn bước sóng ít tải (LL) đã biết và trình bày ba biến thể của thuật toán khe thời gian ít tải (LLT). Các phân tích dựa trên mô phỏng được sử dụng để so sánh kiến trúc TDM đề xuất với các mạng WR truyền thống, cả với và không có chuyển đổi bước sóng. Mục tiêu là so sánh lợi ích của TDM và chuyển đổi bước sóng trong việc cải thiện hiệu suất trong các mạng WR. Kết quả cho thấy việc sử dụng TDM mang lại nhiều lợi ích đáng kể, đặc biệt là cho các mạng đa sợi.

To provide flexibility in deploying new protocols and services, general-purpose processing engines are being placed in the datapath of routers. Such network processors are typically simple RISC multiprocessors that perform forwarding and custom application processing of packets. The inherent unpredictability of execution time of an arbitrary instruction code poses a significant challenge in providing QoS guarantees for data flows that compete for such processing resources in the network. However, we show that network processing workloads are highly regular and predictable. Using estimates of execution times of various applications on packets of given lengths, we provide a method for admission control and QoS scheduling of processing resources. We present a processor scheduling algorithm called estimation-based fair queuing (EFQ) which uses these estimates, and provides significantly better delay guarantees than processor scheduling algorithms which do not take packet execution times into consideration.

Efficient planning and optimization of wavelength division multiplexing networks is an important issue today. Integer linear programming (ILP) is the most used exact method to perform this task. We propose a new ILP formulation that allows to solve optimization with less computational effort compared to other ILP approaches. This formulation applies to multifiber mesh networks with or without wavelength conversion, when either the total fiber number or the total fiber length is the cost function to be minimized. After presenting the formulation we discuss the results we obtained by exploiting it in the optimization of two case-study networks.

The aim of the present paper is to show that stochastic geometry provides an efficient computational framework allowing one to predict geometrical characteristics of large CDMA networks such as coverage or soft-handoff level. The general idea consists in representing the location of antennas and/or mobile stations as realizations of stochastic point processes in the plane within a simple parametric class, which takes into account the irregularities of antenna/mobile patterns in a statistical way. This approach leads to new formulas and simulation schemes allowing one to compute/estimate the spatial averages of these local characteristics in function of the model parameters (density of antennas or mobiles, law of emission power, fading law etc.) and to perform various parametric optimizations.

In this paper, we address the problem of determining an optimal topology for Bluetooth wireless personal area networks (BT-WPAN). In BT-WPAN, multiple communication channels are available, thanks to the use of a frequency hopping technique. The way network nodes are grouped to share the same channel, and which nodes are selected to bridge traffic from a channel to another, has a significant impact on the capacity and the throughput of the system, as well as the nodes' battery lifetime. The determination of an optimal topology is thus extremely important; nevertheless, to the best of our knowledge, this problem is tackled here for the first time. Our optimization approach is based on a model derived from constraints that are specific to the BT-WPAN technology, but the level of abstraction of the model is such that it can be related to the more general field of ad hoc networking. By using a min-max formulation, we find the optimal topology that provides full network connectivity, fulfills the traffic requirements and the constraints posed by the system specification, and minimizes the traffic load of the most congested node in the network, or equivalently its energy consumption. Results show that a topology optimized for some traffic requirements is also remarkably robust to changes in the traffic pattern. Due to the problem complexity, the optimal solution is attained in a centralized manner. Although this implies severe limitations, a centralized solution can be applied whenever a network coordinator is elected, and provides a useful term of comparison for any distributed heuristics.

As the Internet evolves into a ubiquitous communication infrastructure and provides various services including telephony, it has to stand up to the toll quality standards set by traditional telephone companies. Our objective is to assess to what extent today's Internet meets this expectation. Our assessment is based on delay and loss measurements taken over wide-area backbone networks, considers realistic VoIP scenarios and uses quality measures appropriate for voice. Our findings indicate that although voice services can be adequately provided by some ISPs, a significant number of paths lead to poor performance even for excellent VoIP end-systems. This makes a strong case for special handling of voice traffic on those paths. Even on the good paths, rare loss events can occasionally cause perceptible degradation of voice quality. Finally, the appropriate choice of the playout buffer scheme for each path was found to be of critical importance for the perceived quality.

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage and latency, since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync - characteristic polynomial interpolation-based synchronization) predicated upon recent information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity of CPIsync is practical, and that the overall latency is typically much smaller than that of slow sync. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.

With the explosive use of the Internet, contemporary Web servers are susceptible to overloads and their services deteriorate drastically and often cause denial of services. In this paper, we propose two methods to prevent and control overloads in Web servers by utilizing the session-based relationship among HTTP requests. We first exploited the dependence among session-based requests by analyzing and predicting the reference patterns. Using the dependency relationships, we have derived traffic conformation functions that can be used for capacity planning and overload prevention in Web servers. Second, we have proposed a dynamic weighted fair sharing (DWFS) scheduling algorithm to control overloads in Web servers. DWFS is distinguished from other scheduling algorithms in the sense that it aims to avoid processing of requests that belong to sessions that are likely to be aborted in the near future. The experimental results demonstrate that DWFS can improve server responsiveness by as high as 50% while providing QoS support through service differentiation for a class of application environment.

With ubiquitous computing and network access, multiple network conduits are becoming available to mobile as well as static hosts. Selection of the preferred mode of data transfer is a dynamic optimization problem depending on the type of application, its bandwidth/latency/jitter requirements, current network status, cost, power consumption, battery life, and so on. Furthermore, since wireless bandwidth is likely to remain a scarce resource, we foresee scenarios wherein mobile hosts require simultaneous data transfer across multiple IP interfaces to obtain higher overall bandwidth. We present a brief overview of related work identifying schemes that might be applicable to the problem, along with their feasibility, and pros and cons. We then propose a new mechanism to aggregate the bandwidth of multiple IP links by splitting a data flow across multiple network interfaces at the IP level. Our method is transparent to transport (TCP/UDP) and higher layers. We have analyzed the performance characteristics of the aggregation scheme and demonstrated significant gain when the links being aggregated have similar bandwidth and latency. The use of multiple interfaces also enhances reliability. Our analysis identifies the conditions under which the proposed scheme, or any other scheme that stripes a single TCP connection across multiple IP links, can be used to enhance throughput. Several interesting directions for future work have also been identified.