IMA Tea/Reception (with POSTER SESSION)

Monday, January 12, 2004 - 3:40pm - 5:05pm
Lind 400
  • Deterministic Packet Marking for Congestion Price Estimation
    Mark Coates (McGill University)
    Several recent price-based congestion control schemes require relatively accurate path price estimates for successful operation. The proposed addition of the two-bit Explicit Congestion Notification (ECN) field in the IP header provides routers with a mechanism for conveying price information. Recently, two proposals have emerged for probabilistic packet marking at the routers; the proposals allow receivers to estimate path price from the fraction of marked packets. In this poster we introduce an alternative deterministic marking scheme for encoding path price. Under our approach, each router quantizes the price of its outgoing link to a fixed number of bits. We then make use of the IP identification (IPid) field to map data packets to different probe types, and each probe type calculates a partial sum of the path price bits. A router deduces its marking behaviour according to the IPid and the TTL (Time To Live) field of each packet. We evaluate the performance of our algorithm in terms of its error in representing the end-to-end price, and compare it to probabilistic marking. We show that based on empirical Internet traffic characteristics, our algorithm performs better when estimating path price using small blocks of packets.
  • Networks with Multicast Services and Multitype Input Sources
    Wanyang Dai (Nanjing University)
    Multicast and differentiated services are among the most important communication operations and are highly demanded in integrated services packet networks like Internet. When multicast operations are involved, network internal traffic sources generated by multiple copies of a packet in a switch (or a router) and multi-routing requirements of the copies will largely increase the complexity of network performance modeling, analysis, control and scheduling. How to suitably model multicast operations will be a key step in resolving all of the related problems. A way will be presented to address this issue for a network involving both multitype external input sources and shared-memory multicast switches. Issues in general settings and research topics along this direction will be raised.
  • Time-scale Decomposition and Equivalent Rate Based Marking
    Sanjay Shakkottai (The University of Texas at Austin)
    Differential equation models for Internet congestion control algorithms have been widely used to understand network dynamics and the design of router algorithms. These models use a fluid approximation for user data traffic, and describe the dynamics of the router queue and user adaptation through coupled differential equations.

    We show that the randomness due to short and unresponsive flows in the Internet is sufficient to decouple the dynamics of the router queues from those of the end controllers. This implies that a time-scale decomposition naturally occurs such that the dynamics of the router manifest only through their statistical steady-state behavior.

    The interaction between the routers and flows occur through marking, where routers indicate congestion by appropriately marking packets during congestion. We show that the time-scale decomposition implies that a queue-length based marking function such as Random Early Detection (RED) or Random Exponential Marking (REM) have an equivalent form which depend only on the data arrival rate from the end-systems and do not depend on the queue dynamics. This leads to much simpler dynamics of the differential equation models (there is no queueing dynamics to consider), which enables easier simulation (the state space is reduced) and analysis.

    This is a joint work with Yung Yi and Supratim Deb
  • Improving Response Times for Static and Dynamic Web Requests

    We consider how to improve client response times at web sites for both static and dynamic web requests.

    For the case of static Get FILE requests, we propose a simple solution: implementing Shortest-Remaining-Processing-Time (SRPT) scheduling in the Linux kernel. We demonstrate SRPT scheduling improves the expected response time of *every* request [TOCS03, USITS99]. The result is based on analytical work [SIGMETRICS01, SIGMETRICS03] which proves that, counter-to-intuition, helping short requests does not necessarily result in hurting long requests. We also show that SRPT scheduling is particularly effective at combatting transient overload [ITC03].

    For dynamic requests (e.g., e-Commerce, online shopping) response times can be much higher (tens of seconds), due to competition between requests in the backend database. Here we implement preemptive priority scheduling of the database lock queues, providing very low response times for high-priority customers (big spenders), while hardly penalizing low-priority customers [ICDE04, SIGMOD04-in-submission].

  • A Non-Parametric Approach to Generation and Validation of Synthetic Network Traffic
    Kevin Jeffay (University of North Carolina, Chapel Hill)
    In order to perform valid experiments, network simulators and testbeds require source-level traffic generators that correspond to valid, contemporary models of application or user behavior. Unfortunately, the Internet is evolving far more rapidly than our present ability to understand and model the mix and use of applications that account for the majority of bytes transferred on the Internet. We describe a method that automatically generates a source-level model of the mix of TCP applications found on a network link, and show that this model is suitable for generating synthetic traffic in a simulation that is statistically equivalent to traffic in the measured network. The method is novel in that it constructs the model in a non-parametric manner, without any knowledge of the applications present in the network. We validate the method empirically uses traces from our institution and Abilene backbones. The importance of having a method that allows one to faithfully reproduce the source-level characteristics of actual network flows in experiments is illustrated via a case study of active queue management mechanisms (AQM). We demonstrate that dramatically different, and contradictory, conclusions are reached regarding the effectiveness of AQM depending on the types of TCP connections generated in the simulation. This serves as an existence proof that our inability to perform experiments with realistic synthetic traffic makes it difficult, if not impossible, to conclude anything fundamental given the experimental procedures followed at present in most network simulations.

    This is a joint work with F. Hernandez-Campos, A. Nobel, and F.D. Smith
  • Active Network Tomography: Design and Estimation Issues
    George Michailidis
    Estimation of quality of service parameters, such as packet loss rates and delay distributions, is of considerable importance to network administrators and service providers. We consider the active network tomography problem where the goal is to estimate packet loss rates and delay distributions of all internal links in a network from measurements obtained from nodes located on its periphery. This is an example of a large-scale statistical inverse problem. We introduce a new flexible class of probing schemes, which is shown to be computationally efficient for collecting the necessary data in global network monitoring problems. Several methods of estimation for loss rates and delay distributions will be described, including the use of EM-algorithms for the Maximum Likelihood estimators and several classes of least-squares estimates for loss rates. Some practical issues regarding the design of probing experiments on different network topologies and results from simulation studies will also be discussed.