| RECENT TALKS and SEMINARS w/ Audio | Back to Top |
| Congestion Control Architectures, Overlay QoS | Related Papers | Back to Top |
Traditionally QoS capabilities have been constructed out of open-loop building blocks such as packet schedulers and traffic conditioners. In this paper, we consider closed-loop techniques to achieve a range of service differentiation capabilities. Our key contribution is the use of Accumulation-based Congestion Control (ACC) as a data-plane building block to provide an expected minimum rate service which is similar to Frame Relay CIR/PIR and DiffServ assured service. A user with a minimum rate expectation can be interpreted as having a non-concave user utility function. Unfortunately in the context of nonlinear optimization, non-concave utility functions are analytically difficult and often result in multiple optimal solutions. Instead of attempting optimization with non-concave objective functions, we demonstrate a meaningful notion of an expected minimum rate by imposing additional constraints on Kellys convex optimization formulated in [14]. Unlike the constraint which simply requires all user allocations to be larger than their respective expected minima, our constraint does not require admission control. The resulting scheme is distributed, requires each control loop to act only on local knowledge and still allows policy-based control over how capacity is allocated during oversubscription. We use ns-2 simulations and Linux implementation experiments to demonstrate that the service performance matches theoretical results. Our scheme does not require Active Queue Management (AQM) at bottlenecks. However, with AQM, we achieve near zero queue with high utilization.
CONFERENCE SUBMISSION { Postscript | PDF }
This paper generalizes the TCP Vegas congestion avoidance mechanism and proposes a model to use {\em accumulation}, buffered packets of a flow inside network routers, as a congestion measure on which a {\em family} of congestion control schemes can be derived. We call this model accumulation-based congestion control (ACC). We use a bit-by-bit fluid model to define the accumulation concept and develop a general control algorithm which includes a {\em set} of control policies. Then we prove its proportional fairness and global stability. The ACC model serves as a reference for packet network implementations. We show that TCP Vegas is one possible scheme which fits into the ACC model. It is well known that Vegas suffers from round trip propagation delay estimation error and reverse path queuing delay. We therefore design a new scheme called Monaco which solves these problems by employing an {\em out-of-band receiver-based} accumulation estimator, with minimal support from network routers. Analysis and simulation comparisons between Vegas and Monaco demonstrate the effectiveness of the Monaco accumulation estimator. We use ns-2 simulations to show that the static and dynamic performance of Monaco matches the theoretic results. One key issue regarding the ACC model in general, i.e., the scalability of router buffer requirement, is discussed.
This paper generalizes the TCP Vegas congestion avoidance mechanism and proposes a model to use {\em accumulation}, buffered packets of a flow inside network routers, as a congestion measure on which a {\em family} of congestion control schemes can be derived. We call this model accumulation-based congestion control (ACC). We use a bit-by-bit fluid model to define accumulation concept and develop a general control algorithm which includes a {\em set} of control policies. Then we prove its proportional fairness and global stability. The ACC model serves as a reference for packet network implementations. We show that TCP Vegas is one possible scheme which fits into the ACC model. It is well known that Vegas suffers from round trip propagation delay estimation error and reverse path queuing delay. We therefore design a new scheme called Monaco which solves these problems by employing an {\em out-of-band receiver-based} accumulation estimator, with minimal support from network routers. Analysis and simulation comparisons between Vegas and Monaco demonstrate the effectiveness of the Monaco accumulation estimator. We use ns-2 simulations and Linux implementation experiments to show that the static and dynamic performance of Monaco matches the theoretic results. One key issue regarding the ACC model in general, i.e., the scalability of router buffer requirements and a possible solution using a virtual delay queuing mechanism, is discussed and evaluated.
This dissertation presents Edge-to-edge Control (EC), a new traffic control and service differentiation architecture for the Internet. Unlike traditional QoS architectures which require complex scheduling at bottlenecks, EC requires only that intermediate nodes provide FIFO queuing and a separate class for EC traffic. Consequently, EC places no new implementation or upgrade requirements at bottlenecks, requires no new packet format requirements at the IP-level, and requires no upgrades from end-systems. Instead EC concentrates functionality at internetwork edges where existing or proposed building blocks can be employed for traffic control, measurement, policing, congestion-sensitive admission control, congestion-sensitive pricing, and differentiated services. EC operates by establishing closed-loop regulated traffic trunks between EC edges. This traffic trunking building block is called an EC trunk. EC trunks use congestion avoidance to push congestion back from intermediate network nodes distributing the congestion across EC edges where the smaller congestion problems are handled with more stateful and sophisticated methods. We also propose Riviera, a rate-based congestion avoidance algorithm that implements EC trunks.
gzip'd postscript (1592K)
In this work, we focus on the question: How to provide QoS for private networks in an inter-domain multi-provider environment. Traditional QoS mechanisms like diff-serv, CSFQ require deployment of the QoS mechanisms at every potential bottleneck and also require coordination among ISPs. These complex coordination and deployment issues have inhibited the large scale deployment of QoS mechanisms. Our solution is to use a congestion control algorithm to push back all congestion to the edge (e.g access router) and hence called edge-to-edge control algorithm. Then QoS issues like queueing, bandwidth sharing, packet loss distribution are all pushed to the edge, allowing the core to operate using largely stateless mechanisms.
Postscript | PDF | CCR Web Site | Powerpoint Presentation
We propose an explicit rate indication scheme for congestion avoidance in ATM networks. In this scheme, the network switches monitor their load on each link, determining a load factor, the available capacity, and the number of currently active virtual channels. This information is used to advise the sources about the rates at which they should transmit. The algorithm is designed to achieve efficiency, fairness, controlled queueing delays, and fast transient response. The algorithm is also robust to measurement errors caused due to variation in ABR demand and capacity. We present performance analysis of the scheme using both analytical arguments and simulation results. The scheme is being implemented by several ATM switch manufacturers.
Postscript (1.29 MB | Gzip Compressed Postscript (200 KB) | PDF
| TCP Related (Randomization, Rate Control, Modeling, TCP over ADSL): | Related Papers | Back to Top |
A lot of research has {\em separately} considered non-cooperative congestion control, fairness, pricing and differentiated services for the Internet. However, a solution to one of the problems may not be applicable to others. This leads to implementational complexities and is one of the major reason why the proposed solutions are not implemented in real networks. This paper motivates the need for a {\em holistic} approach to jointly solve these design problems and proposes a model using an optimization framework for flow control to achieve these objectives. We argue it is possible to handle all of the above problems by using this model, both from the stand points of theoretical analysis and high level implementation issues.
In this paper we evaluate rate distributions between competing flows in a network of DropTail queues. Specifically we look at the case when some of the flows are non- conformant or mis-behaving and it's effect on conformant flows. Our results show in a network of DropTail queues mis-behaving flows can have significantly higher bandwidth allocations at the cost of conformant flows. Further this unequal sharing worsens in a multi-bottleneck scenario where conformant flows may consistently timeout. However the distribution of rates improves if RED is used at the bottleneck thus suggesting deployment of RED. In this paper we also look at the fairness from the network's perspective rather then end-user's. As such we propose an analytical model for managing non-conformant or mis-behaving flows by manipulating congestion penalties conveyed to them. We show that this penalty transformation can map a user's utility function, $U_s$, to any objective utility function, $U_{obj}$. These penalty transformation modules can be completely implemented at the edge and can also work with Droptail queues. We have analyzed the framework and evaluated it for both single and multi bottleneck scenarios.
K. Chandrayana, "New Architectures for Handling Fairness and
Congestion Response Conformance in the Internet", Doctoral Candidacy
Proposal, ECSE, RPI - May 2003
One of the reasons for the spectacular growth of Internet has been its
ability to support different applications. Though TCP has been the favored
transport protocol, increasingly these applications have using rate
control schemes other than TCP. This flexibility of applications to choose
their rate control schemes presents us with problem of {\em protocol
non-compliance and fairness}. Traditionally, the network design has
coupled the solution of these issues with AQM schemes. However, these AQM
schemes are beset with configuration problems and have not been deployed
on the Internet. In this thesis we present deployable end-system and
edge-system based solutions for protocol compliance and fairness.
Specifically, we propose {\em Randomized TCP} an end-system based solution
for improving fairness in the network and an {\em Edge based Re-marking
framework} for providing protocol compliance and broad range of fairness
objectives in the network.
Though TCP has served the Internet community well it is known to suffer
from a number of phenomena which limit its effectiveness on a network of
Drop Tail queues. The main problems which degrade TCP and network
performance are: synchronization of congestion windows, phase effects,
bias against bursty traffic and unfairness to flows with higher RTTs. In
this thesis we propose an {\em end-system based} solution to some of these
problems. Specifically, we propose to introduce randomization into the
network by randomizing the sending times of packets in TCP and other
similar window based transport protocols. For the TCP case, we call it
{\em Randomized TCP}. In the proposed model, packets of window are sent
after an interval of $RTT(1 + x)/cwnd$, where {\em cwnd} is the congestion
window in packets and {\em x} is a random number drawn from an Uniform
distribution on [-1, 1]. Our results show that this randomization breaks
the synchronization of flows in the network and consequently improves
fairness, reduces burst losses and phase effects.
Though the above proposal works well, its performance is constrained in
presence of selfish flows in the network. Specifically, the area of
concern is protocol conformance, for e.g. TCP-Friendliness. In the present
Internet, the users are free to choose a rate control scheme and act
unilaterally to maximize their network usage. The network on the other
hand wants to allocate resources impartially or according to some
specified criteria (e.g. price, service differentiation etc). However, the
selfish behavior of the users might be in direct conflict with the
objectives of the network. Though AQM schemes have been proposed to
achieve conformance amongst users, they do not {\em always} protect flows
from selfish behavior and are constrained by the range of fairness
criteria they can provide.
In this thesis we look at ``fairness'' from the network's perspective and
focus on managing the distribution of rate allocations. Specifically, we
show that by a penalty transformation we can map a user's utility function
to any target utility function. These penalty transformation agents can be
implemented on the network edges and work with either marking or dropping.
This transformation helps enforce protocol conformance and provides
flexibility to provide a broad range of fairness criteria on the network.
Another advantage of this framework is that it is independent of the
buffer management policy deployed on the network, i.e. it works even on a
network of Drop Tail queues.
In summary this thesis proposes novel end-system and edge-system based
solutions for improving fairness, enforcing congestion response
conformance and managing selfish behavior in the Internet.
Candidacy Proposal | Candidacy Presentation
Current implementations of TCP suffer from performance problems like bias against flows with higher round trip times (RTTs), synchronization of windows, phase effects in flows and correlated losses leading to throughput degradations with Drop Tail queues. In this paper we propose a solution to these issues by introducing randomization into the network through end-to-end congestion control protocols. For the TCP case we call it {\em Randomized TCP}. Instead of sending back-to-back packets, Randomized TCP spaces successive packet transmissions with a time interval $\Delta = RTT(1+x)/cwnd$, where $x$ is a zero mean random number drawn from an Uniform distribution. Randomized TCP, by introducing randomization in the network, reduces synchronization, phase effects and bias against bursty traffic and longer RTT flows, prevalent with current implementations of TCP and Drop Tail Gateways. Our results suggest that by randomizing the sending times we can successfully emulate almost all the beneficial features of RED except congestion avoidance. Moreover, these benefits of randomization can be achieved even when it is partially deployed. We also introduce randomization in Binomial schemes and show performance improvements with Drop Tail queues.
Current TCP implementations employ Additive Increase Multiplicative Decrease (AIMD) as the congestion control mechanism. Recently, a new set of schemes called Binomial Congestion Control Schemes (BCCS) were proposed and a section of these schemes is TCP compliant. In this paper we evaluate the performance of these TCP compliant binomial schemes and show through simulations that AIMD performs better than the other BCCS policies in a wide range networking environments. Specifically, we study the performance of these schemes with respect to throughput, fairness, losses, timeouts and self-similarity. We show that the superior performance of AIMD can be attributed to its more conservative attitude in the presence of losses when it reduces its transmission rate much faster than the other schemes. This results in smaller congestion periods thereby reducing the losses and timeouts which in turn increases the throughput and decreases the degree of self-similarity of the traffic. We also evaluated the performance of TCP Compatible BCCS when they compete with TCP flows. It was found that with sufficiently large number of flows, BCCS competes fairly with TCP. However, with a smaller number of flows in the network TCP flows get smaller share of the bottleneck and disproportionately higher losses and timeouts.
The self-similarity of network traffic has been established in a variety of environments and it is well known that self-similar traffic can lead to larger queueing delays, higher drop rates and extended periods of congestion. In this paper, we investigate the impact of various buffer management algorithms on the self-similarity of network traffic. In this paper we investigate the impact of active and passive queue management policies used at the routers on the self-similarity of TCP traffic. We also propose a modification to the RED algorithm, aimed at reducing the timeouts and exponential backoffs in TCP flows, and show that it can lead to significant reductions in the traffic self-similarity under a wide range of network conditions, as compared to the currently implemented active and passive buffer management policies. We also show that though our techniques are aimed at TCP related causes, it is also effective in reducing the degree of self-similarity in traffic even when application and user level causes are also present, as long as TCP is used as the underlying transport protocol.
Active queue management policies and in particular Random Early
Drop (RED) are being pushed as additional mechanisms in Internet routers
to control congestion and keep network utilization high. RED's performance
is highly dependent on the settings of its control parameters. However, no
firm guidelines exist on configuring RED parameters and the current
suggestions fail to provide the desired performance scalability. In this
paper, we propose a mechanism to configure RED parameters based on
evaluating the expected instantaneous length of a $M^x/M/1/K$ queue. We
show that by setting the RED parameters $min_{th}$ and $max_{th}$ to lie
on either side of this expected queue length, we can ensure that the queue
is not underutilized and flows cut their rates before the onset of
congestion. This setting also allows the operating point to perform
satisfactorily over a wide range of flow counts thereby allowing for a
higher degree of scalability. We also show that our proposed mechanism
increases the queue goodput, reduces losses and timeouts and increases the
fairness when compared to existing guidelines. Our proposals have been
verified using extensive simulations.
Continuing the process of improvements made to TCP through the
addition of new algorithms in Tahoe and Reno, TCP SACK aims to provide
robustness to TCP in the presence of multiple losses from the same
window. In this paper we present analytic models to estimate the
latency and steady-state throughput to TCP Tahoe, Reno and SACK and
validate our models using both simulations and TCP traces collected
from the Internet. In addition to being the first models for the
latency of finite Tahoe and SACK flows, our model for the latency of
TCP Reno gives a more accurate estimation of the transfer times than
existing models. Our models show that under the losses introduced by
the droptail queues which dominate most routers in the Internet,
current implementations of SACK fail to provide adequate protection
against timeouts and a loss of roughly more than half the packets in a
round will lead to timeouts. We also show that with independent
losses, SACK performs better than Tahoe and Reno and as losses become
correlated, Tahoe can outperform both Reno and SACK.
Current models for TCP performance focus mainly on the steady-state
throughput of infinite flows, making them inappropriate for the short
TCP flows which dominate the transfers over the Internet. In this
paper, we present a model for the latency of finite TCP Reno flows
with independent losses for which currently no models exist. The
proposed model can also estimate the steady-state throughput of long
flows. We also present a sensitivity analysis and empirical models
which investigate the effects of various factors like loss rates,
window limitation, delayed acknowledgments and packet size on TCP
latency and quantify and isolate their individual contributions. Our
model captures the effect of timeouts and slow start phases which
occur anywhere during the transfer and uses a more accurate model for
the slow start phase, leading to a more accurate estimation of TCP
latencies.
Most TCP connections in today's Internet transfer data on the order
of only a few KBytes. Such TCP transfers are very short and spend
most of their time in the slow start phase. Thus the underlying
assumptions made by steady-state models cease to hold making them
unsuitable for modeling finite flows. In this paper, we we propose an
accurate model for estimating the transfer times of TCP flows of
arbitrary size. Our model gives a more accurate estimation of the
transfer times than those predicted by [CSAn00], which extends
the steady state analysis of Padhye et al. [PFTK98] to model
finite flows. The main features of out work are the modeling of
timeouts and slow start phases which occur anywhere during the
transfer and a more accurate model for the evolution of the cwnd
in the slow start phase. Additionally, the proposed model can also
model the steady state throughput of TCP connections. The model is
verified using web based measurements of real life TCP connections.
We also introduce an empirical model which allows a better ``feel''
of TCP latency and the nature of its dependence on loss probabilities
and window limitation. Finally, the paper investigates the the effect
on window limitation and packet size on TCP latency.
This paper presents TCP Rate Control, a new technique for {\bf
transparently augmenting end-to-end TCP performance} by controlling
the sending rate of a TCP source. The ``rate'' of a TCP source is
determined by its window size, the round trip time and the rate of
acknowledgments (or acks). TCP rate control controls these aspects by
modifying the ack number and receiver window fields in acknowledgments
and by modulating the acknowledgment rate.
From a performance viewpoint a key benefit of TCP rate control is to
avoid adverse performance effects due to packet losses such as
reduced goodput due to retransmission and timeout delays, and
unfairness or large spread in per-user goodputs. Further, TCP rate
control can positively affect performance even if the {\bf bottleneck
is non-local} and even if the {\bf end-host TCP implementations are
non-conforming}. We demonstrate these aspects through a comparative
study with RED and TCP-ECN, and discuss deployment issues. The TCP
rate control approach has been implemented and patented by Packeteer
Inc.
Related Tech Report in Postscript |
In HTML
We analyze TCP performance in asymmetric networks, where the
throughput significantly depends on the reverse direction and packet
loss. We introduce a new operational model called the "AMP model"
which, with an understanding of TCP dynamics and buffer management
techniques explains the performance effects seen. We apply this model
to guide design improvements in buffer management (ack-regulation) and
scheduling schemes to achieve performance improvements of an order of
magnitude or more. The schemes have been tested through simulation and
implementation, and the module driven improvements observed are better
than those proposed in earlier literature.
This contribution examines different methods of controlling the rate
of TCP applications to achieve the goals of fairness, delay control
and throughput. The key idea is to use an ATM ABR algorithm like
ERICA+ to calculate rate feedback and use new techniques to
control TCP sources using the feedback calculated. Specifically we
propose two rate-to-window translation schemes for explicit window
feedback to TCP and one variant of an acknowledgment bucket scheme
(which controls TCP rate by controlling the rate of
acknowledgements). These techniques can be applied in ATM edge devices
or in Internet routers. We explore the dynamics of TCP traffic under
different methods of rate control and show through simulations that
our techniques can considerably improve fairness, throughput and
end-to-end delay properties of TCP applications.
Postscript (1960KB) |
PKzip Compressed Postscript (255KB bytes) |
PDF |
Packeteer, a company that makes TCP rate-control products
In this paper we present a video communication system that integrates
end-to-end buffer management and congestion control at the source with the
playout adjustment mechanism at the receiver. While each component of the
system has been considered independently in the literature, our focus in
this work is their integration. The proposed system exploits the fact that
when congestion control is implemented at the source, most of the loss
occurs at the source and not within the network. Based on this
observation, we design the buffer management to trade off random loss for
controlled loss of visually less important data. Frame rate is adjusted at
the receiver to maximize the visual quality of the displayed video based
on the overall loss. We tested our system with both H.26L and a
subband/wavelet video coder, and found that it significantly improves the
received video quality in both cases.
Journal version (under review):
PDF
...
PDF
|
NGC Presentation (PPT) |
NGC Presentation (PDF)
Peer-to-peer networks have become extremely popular to provide data-storage
(eg: Napster, Kazaa) or distributed computation facilities (eg: SETI@Home).
We are interested in extending the notion of peer-to-peer networks to
provide a variety of overlay networking services, i.e. by having peers also
provide packet-forwarding capabilities. The performance characteristics
(eg: loss, bandwidth, delay) of such a peer-based overlay network is likely
to be very different and highly variable compared to the traditional
internet end-to-end paths or even traditional managed overlay networks (eg:
Akamai) because packets may cross the Internet several times (for each
overlay hop!). However, the massive diversity, i.e. multiple peer-based
overlay paths (eg: 100s of peer-to-peer overlay paths) harnessed could
compensate for the performance variability of any one path. In addition,
lightweight support at intermediate nodes can improve the single path
performance. In this paper, we focus on the latter problem, i.e. providing
lightweight support at selected intermediate peer forwarding nodes to
achieve dramatically increased error resilience on a single peer-based path
for point-to-point (not multicast!) video-streaming applications. Unlike
traditional error correction that relies on end-to-end ARQ or FEC based
upon the end-to-end error characteristics of the network path, our proposed
scheme is a flexible scheme that also considers the error characteristics
of each overlay hop. However, our scheme is not a heavyweight hop-by-hop
error resilience scheme (like X.25); we segment the end-to-end overlay path
into maximal sized "segments" and provide error resilience between the
overlay nodes (i.e. peers or hosts) of those segments. Therefore we call
our scheme an "overlay multi-hop FEC" (OM-FEC) scheme. Architecturally,
this flexible design lies in between the end-to-end and hop-by-hop
paradigms, and we argue that it is well suited to peer-based overlay
networks. No support is expected from traditional Internet routers. We
evaluate our work in two ways: simulations and real-world implementation on
the worldwide Planetlab infrastructure using a real video streaming
application. Both these evaluations confirm intuition, i.e., providing
lightweight, and flexible multi-hop segment-based FEC can dramatically
outperform a naive pure end-to-end strategy, and can be much more efficient
than a heavyweight naive hop-by-hop resilience strategy.
Peer-to-peer based multimedia delivery is becoming increasingly more
important in today's networks. Using a peer-to-peer network to assist video
streaming is a topic of considerable interest. In this paper, we propose a
novel hybrid video downloading/streaming scheme (HDS) that efficiently
integrates traditional client/server based video streaming and peer-to-peer
based media distribution. Furthermore, we propose a receiver-driven
algorithm to coordinate the downloading and streaming modes; and control
the state transitions between these modes. We have performed real-world
experiments and simulations to validate our concept. These results show
that our proposed scheme greatly increases the availability of video
content on the receiver side and simultaneously reduces the server load
significantly.
In this paper we address the issue of efficient multimedia
streaming by integrating an intelligent buffer management
scheme with the congestion control scheme at the source. The
scheme exploits the fact that most of the transmission losses actually
occur at the source and not in the network. An intelligent
transmission scheme can take advantage of this fact and thus control
exactly what data is dropped in response to network congestion.
The integrated model uses priority information from the encoder
and network information from the congestion scheme and
drops low priority packets and sends the most important packets
in the available bandwidth. The packets are dropped when the
source transmission buffer length exceeds a minimum threshold.
This scheme ensures that the media transmitted has the highest
possible quality under the given network conditions using a given
coding scheme. This paper also presents a randomized transmission
scheme as part of the integrated model to reduce the jitter and
burst losses in the multimedia transmissions.
TBA...
A typical method to perform single-rate multicast congestion control
is for the source to adapt the sending rate to the most congested
path. In previous research, TCP throughput formula is used to estimate
the expected throughput of all paths for locating the most congested
one. In order to measure RTT used in the formula, the source needs to
exchange packets with every receiver. In sequence, there can be
feedback implosion. In this article, we try to solve this problem by
proposing a new method to locate the most congested path, where the
source only needs to send packets. In this new method, the average
attenuation factor (AAF) (of throughput) is measured for each path in
the multicast tree, and the path with the highest AAF is considered as
the most congested. AAF describes how much and how often the input of
a path is attenuated on its route. Its formal definition is presented
as a part of this paper. By simulations, we verify the properties of
AAF and show the effectiveness of our proposed method as well. Using
AAF to locate the most congested path can be used as a building block
in multicast congestion control. Once the path is located, the source
can adjust its sending rate using different policies based on the
feedback from the receiver behind this path.
In this article, we propose a new single-rate multicast congestion
control scheme called ORMCC based on a new metric, TRAC (Throughput
Rate At Congestion). The scheme is simple: states maintained at source and
receivers are O(1); only simple computation is required; and there is
no need to measure RTTs from all receivers to the source. At the same
time, the scheme is TCP-friendly, does not suffer from drop-to-zero
problem, and is very effective with feedback suppression. Theoretical
analysis of the scheme performance is provided, and simulations have
shown that ORMCC outperforms PGMCC and TFMCC under most situations. We
have also implemented ORMCC on top of UDP and successfully run it on
real systems in Emulab with promising results.
In this paper, we propose MCA, an end-to-end multicast congestion
avoidance scheme with feedback suppression. Congestion avoidance is
different from congestion control in the sense that our scheme detects
and responds to network congestion without necessarily inducing packet
loss. Our scheme is a single-rate scheme and operates end-to-end,
i.e., it goes at the rate allowed by the worst congested receiver and
does not expect packet marking or other support from intermediate
nodes. We design it to be robust under both lossless and lossy
situations. Congestion is detected at receivers using the concept of
``accumulation'' (the number of buffered bits of a flow inside the
network) and simple thresholding techniques proposed in our recent
unicast work. For the purposes of representative (the worst congested
receiver) selection by the source and feedback suppression, each
receiver maintains its Good Throughput Rate At Congestion (G-TRAC)
(the product of receiving rate during congestion epochs and (1 - p),
where p is congestion occurrence frequency). In this way, receivers
do not need to continuously (either densely or sparsely) exchange
packets with the sender (e.g. to measure RTT). Therefore, MCA is
scalable for large-size groups. We evaluate the design and demonstrate
the performance of MCA using detailed ns-2 simulations.
We propose MCA, a rate-based end-to-end multicast congestion scheme.
Congestion avoidance is different from congestion control in the sense
that our scheme detects and responds to network congestion without
necessarily inducing packet loss. Our scheme is a single-rate scheme
and operates end-to-end, i.e., it goes at the rate allowed by the
worst congested receiver and does not expect packet marking or other
support from intermediate bottlenecks. Congestion is detected
autonomously at receivers using the concept of "accumulation"
and simple thresholding techniques proposed in our recent unicast
work. Congestion feedback to senders can be in the form of single-bit
congestion indication (CIs) or as a multi-bit output rate measure. The
feedback is sparse in the sense that at most one feedback is generated
per measurement period (unlike multiple loss indications generated
during packet loss). The source implements two key blocks: a filtering
block to discriminate between competing feedback from receivers, and a
congestion response block which implements a rate-increase/decrease
policy. The two different feedback models (bit-based or explicit
rate-based) leads to two different schemes: bit-based and explicit
rate-based schemes. Simulation results show that both schemes avoid
the drop-to-zero problem and are fair with unicast congestion
avoidance schemes.
GZIP Postscript |
Postscript |
PDF
We propose an end-to-end single-rate source-based multicast
congestion control scheme (LE-SBCC) for reliable or unreliable
multicast transport protocols. It addresses key issues such as
drop-to-zero issues, TCP friendliness
and RTT estimation. The scheme consists of a cascaded
set of filters and a rate adaptation policy module (AIMD or TFRC)
which transform the multicast tree to appear like a
unicast path for the purposes of congestion control. The scheme is not
self-clocked but acts upon a stream of loss indications (LIs), which
are filtered to get a stream of loss events (LEs) (at most
one per RTT per receiver). This LE stream is further filtered to
extract the maximum LEs from any one receiver, which results in at most
one rate-reduction per RTT. A range of results
(simulation and experimental) is presented and compared against the
mathematical model of the scheme components.
Postscript |
GZIPPED Postscript |
PDF
This paper presents a simple, generic source-based end-to-end
multicast congestion control (GSC) algorithm for reliable multicast
transport (RMT) protocols. The algorithm is completely implemented at
the source and leverages the reverse control information flow in RMT
protocols like PGM or RMTP. Specifically, it does not introduce any
new control traffic or new fields in RMT protocol headers. It
addresses the drop-to-zero problem in limited cases by introducing a
robust, adaptive time-filter based upon RTT estimates collected by
observing NAK traffic. This solution allows it to be very adaptive to
congestion situation changes in any part of the tree. The algorithm is
friendly to TCP in terms of competition for bandwidth shares. The
scheme has minimal control traffic requirements and weak RTT
estimation requirements which allows a large deployment space
including multi-sender multicast and combination with receiver-based
schemes.
Postscript |
Gzipped Postscript |
PDF
Congestion control is a key requirement for reliable multicast
transport (RMT) protocols. We have recently developed a purely
source-based scheme (GSC) which requires no receiver/network
support. This paper extends that work to handle high degrees
of multiplexing and reasonably large receiver sets and demonstrates the
TCP friendliness of the scheme.
Abstract (PS) |
Summary (PS) |
NGC site |
Poster Slides (PPT)
Today the Internet offers a single path between end-systems even
though it intrinsically has a large multiplicity of paths. This paper
proposes an evolutionary architectural framework ``BANANAS'' aimed at
simplifying the introduction of multipath routing in the Internet. The
framework starts with the observation that a path can be encoded as a
short hash (``PathID'') of a sequence of globally known
identifiers. The PathID therefore has global significance (unlike MPLS
or ATM labels). This property allows multipath capable
nodes to {\em autonomously} compute PathIDs in a partially upgraded
network without requiring an explicit signaling protocol for path
setup. We show that this framework allows the introduction of
sophisticated explicit routing and multipath capabilities within the
context of widely deployed connectionless routing protocols
(e.g. OSPF, IS-IS, BGP) or overlay networks. We establish these
characteristics through the development of PathID encoding and
route-computation schemes. The BANANAS framework also allows
considerable flexibility in terms of architectural function placement
and complexity management. To illustrate this feature, we develop an
efficient variable-length hashing scheme that moves control-plane
complexity and state overheads to network edges, allowing a very
simple interior node design. All the schemes have been evaluated
using both sizable SSFNet simulations and Linux/Zebra implementation
evaluated on Utah's Emulab testbed facility.
Postscript (older version) |
PDF (latest) |
SIGCOMM FDNA (Aug 2003) Powerpoint (PPT) Slides |
Paper Summary & Highlights (REAL AUDIO |
MP3)
Internet data traffic is doubling each year, yet bandwidth does not
appear to be growing as fast as expected and thus short falls in
available bandwidth, particularly at the ``last mile'' may result. To
address these bandwidth allocation and congestion problems,
researchers are proposing new overlay networks that provide a high
quality of service and a near lossless guarantee. However, the central
question raised by these new services is what impact will they have in
the large? To address these and other network engineering research
questions, high-performance simulation tools are required. However, to
date, optimistic techniques have been viewed as operating outside of
the performance envelope for Internet protocols, such as TCP, OSPF and
BGP.
Performance analysis techniques are fundamental to aid the process of
large-scale protocol design and network operations. There has been a
tremendous explosion in the variety of tools and platforms available
(eg: ns-2, SSFNet, Click Router toolkit, Emulab, Planetlab). However,
we still look at the sample results obtained from such tools with
skepticism because they are isolated (potentially random) and may not
be representative of the real-world. The first issue (random isolated
results) can be addressed by large-scale experiment design techniques
that extract maximum information and confidence from a minimum number
of carefully designed experiments. Such techniques can be used to find
``good'' results fast to guide either incremental protocol design or
operational parameter tuning. The second issue (representativeness) is
more sticky and relates to formulating benchmarks. In this paper, we
explore the former case, i.e. large-scale experiment design and
black-box optimization (i.e. large-dimensional parameter state space
search). We propose a new platform ROSS.Net that combines large-scale
network simulation with large-scale experiment design and XML
interfaces to data sets (eg: Rocketfuel, CAIDA) and models (traffic,
topology etc). This is a step towards the broader problem of understanding
meta-simulation methodology, and speculate how we could integrate
these tools with testbeds like Emulab and Planetlab. Examples of
large-scale simulations (routing, TCP, multicast) and experiment
design are presented.
ROSS.Net brings together the four major areas of networking research:
network modeling, simulation, measurement and protocol design.
ROSS.Net is a tool for computing large scale design of experiments
through components such as a discrete-event simulation engine, default
and extensible model designs, and a state of the art XML interface.
ROSS.Net reads in predefined descriptions of network topologies and
traffic scenarios which allows for in-depth analysis and insight into
emerging feature interactions, cascading failures and protocol
stability in a variety of situations. Developers will be able to
design and implement their own protocol designs, network topologies
and modeling scenarios, as well as implement existing platforms within
the ROSS.Net platform. Also using ROSS.Net, designers are able to
create experiments with varying levels of granularity, allowing for
the highest-degree of scalability.
The parameter configuration of a network protocol can be formulated as
a black-box optimization problem with network simulation evaluating
the performance of the black-box, i.e., the network. This paper
proposes a unified search framework (USF) to handle such large-scale
black-box optimization problems. The framework is designed to provides
a generalized platform on which specifically tailored optimization
algorithms can be constructed easily for various types of problems. Therefore, it can be
applied to the configuration of different network protocols. In the
USF, various samplers are provided as basic building blocks and each
of them implements a certain search technique. For a specific problem,
a selection of samplers can be used to construct an appropriate search
algorithm. These samplers are run in parallel and coordinated with
various type of memories which selectively store the samples generated
by samplers. The USF also include a resource management mechanism,
which can manage parallel computing devices, for example, a network of
workstations, and allocate the available computing resources to
samplers according to the predefined allocation strategy. The
benchmark tests are presented in this paper to demonstrate the
flexibility and advantages of the USF.
Simulation of large-scale networks remains to be a challenge, although
various network simulators are in place. In this paper, we identify
fundamental issues for large-scale network simulation, and propose new
techniques that address them. First, we exploit optimistic parallel
simulation techniques to enable fast execution on inexpensive
hyper-threaded, multiprocessor systems. Second, we provide a compact,
light-weight implementation framework that greatly reduces amount of state
required to simulate large-scale network models. Based on the proposed
techniques, we provide sample simulation models for two networking
protocols: OSPF and TCP. We implement these models in a simulation
environment ROSSNet, which is an extension to the previously
developed optimistic simulator ROSS. We perform validation experiments for
TCP and OSPF, present performance results of our techniques by
simulating OSPF and TCP on a large and realistic topology, such as AT\&T's
US network based on Rocketfuel data. The end result of these innovations
is that we are able to simulate million node network topologies using
commercial off-the-shelf hyper-threaded multiprocessor systems costing
less than $7000 USD, and consumes less than 1.4GB of RAM in total.
Parameter configuration is a common procedure used in large-scale
network protocols to support multiple operational goals. This problem
can be formulated as a black-box optimization problem and solved with
an efficient search algorithm. This paper proposes a new heuristic
search algorithm, Recursive Random Search(RRS), for large-scale
network parameter optimization. The RRS algorithm is based on the
initial high-efficiency property of random sampling and attempts to
maintain this high-efficiency by constantly ``restarting'' random
sampling with adjusted sample spaces. Due to its root in random
sampling, the RRS algorithm is robust to the effect of random noises
in the objective function and is advantageous in optimizing the
objective function with negligible parameters. These features are very
important for the efficient parameter optimization of network
protocols. The performance of RRS is demonstrated with the tests on a
suite of benchmark functions. The RRS algorithm has been
applied to the adaptive configuration of several network protocols,
such as RED, OSPF and BGP. One example application in OSPF routing
algorithm is presented.
As the Internet infrastructure grows to support a variety of services
(eg: VPNs), its legacy protocols (eg: OSPF, BGP) are being overloaded
with new functions such as traffic engineering. Today, operators
engineer such capabilities through clever, but {\em manual} parameter
tuning. In this paper, we propose a back-end support tool for
large-scale parameter configuration that is based on efficient
parameter state space search techniques and online simulation. The
framework is useful when the network protocol performance is sensitive
to its parameter settings, and its performance can be reasonably
modeled in simulation. In particular, our system imports the network
topology, relevant protocol models and latest monitored traffic
patterns into a simulation that runs online in a network operations
center (NOC). Each simulation evaluates the network performance for a
{\em particular setting} of protocol parameters. A recursive random
search (RRS) technique is proposed to explore the large-dimensional
parameter state space, where each sample point results in a single
simulation. In other words, the overall parameter configuration
problem is modeled as a {\em ``black-box'' optimization} problem. The
goal of RRS is efficiency, i.e., to find {\em ``good''} network
protocol configurations for the current traffic conditions {\em
quickly}. An important feature of the framework is its flexibility: it
allows arbitrary choices in terms of the simulation engines used (eg:
ns-2, SSFnet, future scalable simulators etc), network protocols to be
simulated (eg: OSPF, BGP, RED, MPLS etc), and in the specification of
the optimization objectives. We demonstrate the flexibility and
relevance of this framework in three scenarios: joint tuning of the
RED buffer management parameters at multiple bottlenecks, traffic
engineering using OSPF link weight tuning, and outbound
load-balancing of traffic at peering/transit points using BGP
LOCAL\_PREF parameter. The first application (RED) is prototyped and
evaluated in a Linux-based testbed using SNMP as the configuration
interface.
This paper proposes a new heuristic search algorithm, Recursive Random
Search(RRS), for black-box optimization problems. Specifically, this
algorithm is designed for the dynamical parameter optimization of
network protocols which emphasizes on obtaining good solutions within
a limited time frame rather than full optimization. The RRS algorithm
is based on the initial high-efficiency property of random sampling
and attempts to maintain this high-efficiency by constantly
``restarting'' random sampling with adjusted sample spaces. Due to its
basis on random sampling, the RRS algorithm is robust to the effect of
random noises in the objective function and it performs especially
efficiently when handling the objective functions with negligible
parameters. These properties have been demonstrated with the tests on
a suite of benchmark functions. The RRS algorithm has been
successfully applied to the optimal configuration of several network
protocols. One application to a network routing algorithm is
presented.
Traffic engineering broadly relates to optimization of the operational
performance of a network. This survey discusses techniques like
multi-path routing, traffic splitting, constraint-based routing,
path-protection etc. that are used for traffic engineering in
contemporary Internet Service Provider (ISP) networks. These
techniques can be classified under two broad classes, connectionless
and connection-oriented, that dominate the current debate on
next-generation routing and traffic engineering in IP networks. The
connectionless approach evolves current distance-vector and link-state
algorithms, or influences routing metrics. The connection-oriented
approach uses signaling and is being used by techniques like Multi
Protocol Label Switching (MPLS). Connection-oriented techniques offer
a convenient way to monitor, allocate, reroute, and protect resources
for a given traffic on an explicit and flexible basis. This survey
will examine the core problems, discuss solutions in both
connectionless and signaled approach, and point to topics for research
and advanced development.
In this paper, we present an OSPF weights optimization scheme using a
general automatic network management framework proposed recently,
i.e., an on-line simulation framework. We have chosen the
packet drop rate in the network as the optimization metric as it is a
good indicator of congestion in the network and also impacts the
performance of the underlying applications. The packet drop rate has
been formulated in terms of the link parameters, such as bandwidth and
buffer space, and the parameters of the traffic demands. A GI/M/1/K
queuing model has been used to compute the packet drop probability on
a given link. We have also developed a fast recursive random search
algorithm to address the issues associated with network optimization
problems. The search algorithm has been compared to the local search
heuristic of \cite{Thorup} in terms of the number of function
evaluations needed to obtain a ``good'' OSPF link weight setting. Our
results demonstrate that the recursive random search takes 50-90\%
fewer function evaluations to find a ``good'' setting. The amount of
improvement depends on the network topology, traffic conditions and
optimization metric. We have simulated the proposed OSPF optimization
scheme in $ns$\cite{ns} and the results indicated improvements of the
order of 30-60\% in the total packet drop rate.
PS |
PDF |
PDF (shortened version)
Random Early Detection (RED) is an active queue management mechanism
designed to provide better performance than traditional
DropTail. However, its parameter setting has proved to be very
sensitive to network scenarios and needs constant tuning to achieve
ideal performance under varying network conditions. In view of the
fact that RED has not been understood well enough for an analytical
approach, this paper takes advantage of network simulation techniques
and formulates the optimal configuration of RED as a black-box
optimization problem. An optimization objective is designed to
effectively reflect the tradeoff between utilization and queueing
delay. Based on the proposed RED optimization scheme, a general
automatic network management system, i.e., on-line simulation
system[1], has been used for the on-line tuning of RED under changing
network conditions. The proposed approach is empirically validated
with simulations and real network experiments. The simulation results
show that RED controlled with on-line simulation system is able to
stabilize around the expected equilibrium status under varying
conditions and maintain high utilization.
The complex, dynamic nature of the Internet requires scalable,
effective network management. This paper proposes a dynamic network
management architecture, which performs the parameter tuning of the
underlying network protocols based upon collaborative on-line
simulation, thus achieving second-order control over the network. This
paper presents the various components of the architecture,
optimization techniques and a proof-of-concept implementation with the
RED algorithm.
Several adaptive pricing proposals have been made in the last decade for
the Internet. Usually, however, those proposals studied optimal strategies
and did not focus on implementation issues. We address implementation
issues for adaptive pricing over a single differentiated-services
(diff-serv) domain. We propose a new adaptive pricing framework
Distributed Dynamic Capacity Contracting (Distributed-DCC), which is
deployable over diff-serv architecture of the Internet. Essence of
Distributed-DCC is to employ edge-to-edge coordination along with
techniques for estimation of user willingness-to-pay (e.g. budget
estimation). Particularly, congestion can be detected on an edge-to-edge
basis, which enables congestion-sensitive pricing at the edges.
Distributed-DCC is able to provide a range of weighted fairness types
(i.e. from max-min to proportional) in rate allocation by using pricing as
a tool. The provider can tune a parameter, fairness coefficient, to change
fairness of the framework.
To illustrate possibility of congestion-sensitive pricing in the
framework, we develop a congestion-sensitive pricing scheme, Edge-to-Edge
Pricing (EEP), within the framework. We derive optimal prices for EEP and
investigate effects of user's elasticity on these optimal prices.
We also investigate congestion control by pricing, especially in terms of
time-scale. We illustrate that control of congestion by pricing requires
very small time-scale pricing (i.e. frequent updates to prices), which
complicates human involvement into negotiations. To solve this time-scale
problem, we propose two pricing architectures: Pricing for Congestion
Control (PFCC) and Pricing over Congestion Control (POCC). PFCC uses small
time-scale pricing directly for controlling congestion and employs
end-placed software/hardware agents which take inputs from human user at
large time-scale while negotiating with the provider at small time-scale
on behalf of the user. POCC uses an underlying edge-to-edge congestion
control mechanism by overlaying pricing on top of it. This way, POCC
controls congestion at small time-scales while allowing pricing at
time-scales large enough for human involvement. We also illustrate how to
adapt Distributed-DCC to these architectures.
Several congestion pricing proposals have been made in the last decade.
Usually, however, those proposals studied optimal strategies and did not
focus on implementation issues. Our main contribution in this paper is to
address implementation issues for congestion-sensitive pricing over a
single differentiated-services (diff-serv) domain. We propose a new
congestion-sensitive pricing framework Distributed Dynamic Capacity
Contracting (Distributed-DCC), which is able to provide a range of
fairness (e.g. max-min, proportional) in rate allocation by using pricing
as a tool. We develop a pricing scheme within the Distributed-DCC
framework and investigate several issues such as optimality of prices,
fairness of rate allocation.
We also introduce two pricing architectures based on the manner of using
pricing to control congestion: Pricing for Congestion Control (PFCC) and
Pricing over Congestion Control (POCC). PFCC uses pricing directly for
controlling congestion, whilst POCC uses an underlying edge-to-edge
congestion control mechanism by overlaying pricing on top of it. We, then,
adapt Distributed-DCC framework to these architectures, and evaluate the
two architectures by extensive simulation.
In order to provide better Quality-of-Service (QoS) in large networks,
several congestion pricing proposals have been made in the last decade.
Usually, however, those proposals studied optimal strategies and did not
focus on implementation issues. Our main contribution in this paper is to
address implementation issues for congestion-sensitive pricing over a
single domain of the differentiated-services (diff-serv) architecture of
the Internet. We propose a new congestion-sensitive pricing framework
Distributed Dynamic Capacity Contracting (Distributed-DCC), which is able
to provide a range of fairness (e.g. max-min, proportional) in rate
allocation by using pricing as a tool. Within the Distributed-DCC
framework, we develop an Edge-to-Edge Pricing Scheme (EEP) and present
simulation experiments of it.
In the current bandwidth market, Internet Service Providers (ISPs)
provide guaranteed Internet bandwidth within their domains. However,
they are incapable of providing such assurances for data crossing
their domain boundaries. In this paper, we present a spot pricing
scheme for Internet bandwidth contracts within an ISP domain. These
models when implemented at access or exchange points of different ISP
domains would provide assured bandwidth for inter-domain traffic. Each
contract will constitute a Quality of Service agreement between a
customer and a provider within an ISP domain. By appropriately
bundling derivative contracts defined on the intra-domain service
contracts, a provider will not only be able to give inter-domain
Quality of Service assurance, but will be able to add new services and
manage its portfolio of services.
One of the biggest obstacles for implementing congestion pricing is the
pricing time-scale. The Internet traffic is highly variant and hard to
control without a mechanism that operates on very low time-scales, i.e. on
the order of round-trip-times (RTTs). However, pricing naturally operates
on very large time-scales because of human involvement. So, in order to
put tight control on congestion through pricing, new implementation
methods and architectures are needed for congestion pricing. In order to
solve this problem, we propose a novel approach Pricing over Congestion
Control (POCC). The essence of POCC is to overlay congestion pricing on
top of an underlying congestion control scheme which enforces a much
tighter control than pricing. This way congestion in the interior network
is controlled very tightly, while pricing is done at time-scales large
enough to incorporate human involvement. %We investigate the problems
raised within such an overlay architecture and provide solutions to them.
We particularly focus on diff-serv and use edge-to-edge congestion control
and edge-to-edge pricing techniques to illustrate POCC ideas in
simulation.
Static optimization of networks by pricing has attracted significant
attention over the last decade. These studies assumed concave utility
functions for users and derived optimal pricing strategies for the
network
provider. In this paper, we consider effect of user's elasticity to
price
and bandwidth on optimality of pricing. We first derive optimal
pricing
strategy for the case of logarithmic user utilities. Then, we
investigate
two types of elasticity for users: Demand-price elasticity and
utility-bandwidth elasticity. By incorporating these two elasticities,
we
develop a non-logarithmic utility function for users. Finally, we
derive
an optimal pricing strategy for the non-logarithmic user utilities and
illustrate that pricing strategy should be more conservative when the
elasticities increase.
One of the key issues for implementing congestion pricing is the
pricing granularity (i.e. pricing interval or time-scale). The
Internet traffic is highly variant and hard to control without a
mechanism that operates on very low time-scales, i.e. on the order of
round-trip-times (RTTs). However, pricing naturally operates on very
large time-scales because of human involvement. Moreover, structure of
wide-area networks does not allow frequent price updates for many
reasons, such as RTTs are very large for some cases. In this paper, we
investigate the issue of pricing granularity, identify problems, and
propose solutions.
Extended version: "Effect of Pricing Intervals on Congestion-Sensitivity of Network Prices", Submitted to Telecommunication Systems, 2003.
PDF
In this paper we present a baseline
implementation strategy for the well-known Smart Market pricing scheme on
diff-serv. Our strategy tries to violate Smart Market's theoretically
defined properties as less as possible. In order to suit diff-serv
framework, we propose ways of focusing Smart Market's complex operations
at the edges while keeping the interior simple. Based on the proposed
implementation strategy, we develop packet-based simulation of Smart
Market. By simulation, we then investigate Smart Market's performance in
terms of stability, fairness, and service differentiation on UDP and TCP
traffic. We also look at importance of packet sorting (i.e. sorting of
packets at routers according to their bids as proposed in Smart Market) in
Smart Market's performance. By several simulations, we find that packet
sorting does not really improve the performance for all the three metrics
(stability, fairness, and service differentiation). So, it is not
necessary to implement packet sorting, which significantly reduces
necessary router upgrades for Smart Market's possible deployment.
Congestion-sensitive pricing for providing better than best effort service
has received significant attention in the last decade. In this paper we
identify a robust parameter for capturing congestion conditions in an
edge-to-edge framework and propose a family of adaptive pricing schemes
for premium network services. The parameter is the ratio of two values:
Edge queue and estimated edge-to-edge capacity. By
coordination between edge routers, both of the values are available at the
ingress point in an edge-to-edge framework. Thus, the pricing schemes
deployable. Based on the identified parameter, we propose a new adaptive
pricing framework, Price Discovery. Based on the Price Discovery framework
and the identified pricing parameter, we develop and analyze four pricing
schemes. We compare the pricing schemes, and select the best one in
performance. We identify stability conditions for the best scheme. This is
followed by evaluation of the best pricing scheme with extensive
simulations of various scenarios.
Dynamic pricing techniques attracted significant attention as tools to
implement better resource sharing, and address the issue of congestion in
the Internet. Among the pricing schemes, the "smart market" is a purely
congestion-sensitive scheme, which makes it a basis for comparing new
pricing schemes. However, there are significant implementation challenges
in this scheme. We investigate these issues and come up with an
implementation strategy in the differentiated-services architecture. This
strategy involves certain changes to the scheme and limitations on the
traffic types. This paper reports our implementation strategy, scheme
changes, and simulation results illustrating the performance of the smart
market scheme.
Internet pricing is receiving increased attention in industry and
academia. In this paper, we report the results of comparing two
Internet pricing models. Using simulation techniques, we evaluate the
technical and economic efficiencies of the Smart Market model proposed
by MacKie-Mason & Varian (1993) and compare it with Dynamic Capacity
Contracting, a pricing scheme that we have developed. Dynamic Capacity
Contracting is a congestion-sensitive pricing model implementable in
the differentiated services architecture of the Internet. The central
idea of congestion-sensitive pricing is that, based on congestion
monitoring mechanisms, a network could raise prices and vary contract
terms dynamically. Our results indicate that while the smart market
model achieves a higher economic efficiency, it results in poor
technical performance of the network. On the other hand, the dynamic
contracting model achieves a better balance of economic and technical
efficiencies. We discuss the implications of our work and identify
future research directions.
In this paper we propose an edge-based quality of service architecture
aimed at site-to-site private networks over the Internet. We extend
the traditional point-to-point service model to a point-to-set service
model, assuming a finite, bounded set of destination sites. Instead of
provisioning point-to-point links between a source and its set of
destinations, a point-to-set service allows the user to have an
allocated bandwidth, which could be flexibly assigned to traffic going
toward any destination within the set. The proposed point-to-set
service provides low loss rates and flexibility to users while
allowing providers to obtain multiplexing gains by employing a
probabilistic admission control test. Simulation results are provided
to demonstrate the utility of deploying such a model.
We examine a range of edge-based services that can help provide
Quality of Service assurances to flows over the Internet. The
main theme of these solutions is the approach of keeping the
network core simple and resorting to knowledge of traffic statistics
to make decisions at the network edge.
In this paper we propose an edge-based quality of service (QoS)
architecture aimed at site-to-site private networks over the Internet. We
extend the traditional point-to-point service model to a point-to-set
service model, assuming a finite, bounded set of destination sites. A
point-to-set service allows a user to have a pool of premium tokens, which
could be flexibly assigned to traffic going towards any destination within
the set. The proposed point-to-set service provides statistical assurances
and flexibility to users while allowing providers to obtain multiplexing
gains. To realize the point-to-set service model, we introduce edge-based
dynamic bandwidth tracking and provisioning schemes. The tracking
algorithm predicts demand towards a given destination edge. This
information is used to efficiently allocate bandwidth towards the
destinations in the set. Simulation results are presented to demonstrate
the merits of the proposed architecture in terms of cost savings to the
customer and efficient resource utilization to the provider.
GZIP Postscript |
GZIP Postscript |
PDF
This paper proposes the use of TCP-aware network-based packet marking,
which in conjunction with differential packet dropping, is a powerful
way to scale the performance of buffer management for best-effort
services on the Internet. In particular, we extend the notion of
``TCP-Friendly'' packet marking, proposed recently by us, and
apply it to improve the performance of traditional best-effort
services. The TCP-aware use of deterministic packet marking at the
enterprise edge allows us to protect selected TCP packets from
suffering loss, thus significantly reducing the total number of
timeouts and avoiding the resulting service degradation. In
particular, we protect TCP sessions with very small windows, disperse
packet loss across a given window, and protect retransmitted packets
from encountering loss. We show baseline results which illustrate that
the performance gains are considerable (orders of magnitude) when
compared to stateful packet dropping algorithms like FRED, and even
when TCP SACK implementations are employed. The scheme has been
implemented in Linux 2.2.10, and all the results are based upon
experimental data.
CCR Web Site |
Postscript |
Gzipped Postscript |
PDF |
Technical Report (PS+zip) |
Technical Report (PDF+zip)
The differentiated services architecture allows the provision of
``better-than-best-effort'' services in the Internet. However, the
performance of legacy TCP applications over differentiated services
is still influenced by bursty packet loss behavior. This paper
proposes the use of TCP-friendly building blocks in the diff-serv
architecture, and in particular, a TCP-friendly traffic marker to
enhance TCP performance over assured service. We present the marker
design and resulting performance improvements in terms of improved
predictability of service, reduced provisioning requirements, better
fairness and fewer TCP timeouts. Though the marker improves assured
service performance predictability compared to a simple token bucket
marker, the performance is still dependent to some extent on TCP
dynamics.
Postscript |
Gzipped Postscript |
PDF |
Presentation (ppt)
This document proposes the use of one bit in the DS-byte to
facilitate ECN-type control in the differentiated services
architecture. Specifically during periods of congestion along a
flow's path (indicated using the one-bit mechanism), the out-of-
profile packets of the flow (packets for which the "In profile" bit
is cleared) can be either delayed or dropped by the ingress network
edge routers. This scheme would allow interior routers to preserve
their resources for processing in-profile packets during congestion
and guard against certain types of denial-of-service attacks. The
proposed mechanism could also be used to build differentiated
services networks with lower average delay, and aid the
implementation of congestion-based pricing schemes in such
architectures. The mechanism interoperates well with the baseline
differentiated services architecture and can also interoperate with
ECN-TCP and future ECN-enabled transports/applications. Further, the
ECN-type flow control can be deployed within a differentiated
services network even if end-to-end ECN support is unavailable,
allowing a quick migration path.
Text (38KB)
An H-infinity based robust controller is designed for a rate-feedback
flow-control problem in single-bottleneck data-communication
networks. The controller is robust to uncertain time-varying multiple
time-delays in different channels. The controller forces the queue
length at the bottleneck node to the desired steady-state value
asymptotically and also satisfies a weighted fairness condition. Lower
bounds for stability margins for uncertainty in the time-delays and
for the rate of change of the time-delays are derived. A number of
simulations are included to demonstrate the time-domain performance of
the controller. Trade offs between robustness and time-domain
performance are also discussed.
In this paper, we investigate the use of capacity information in the
H-infinity controller design for rate-based flow control in high-speed
networks for the case of a single bottleneck node and a single
queue. In the previous works in this line of research, it was assumed
that the controller has access to queue information, and robust
controllers were designed for queue management, under time-varying
time delay uncertainties. Here we assume that, besides the queue
information, the controller has access to capacity. On top of the
existing robust controller, we use an additional controller term,
acting on the capacity information. We investigate optimal ways to
design such additional controller terms.
In this paper we consider the effect of timedelay in the performance
of the AIMD algorithm, specifically queue length and fairness for both
rate and window based sources. The queue bounds can be used to
allocate buffers at bottlenecks so that flows can go through without
any loss.We modify the AIMD algorithm by making the additive rate
increase parameter proportional to the round trip time and the
decrease parameter proportional to the power of round trip time which
makes the algorithm fair even with heterogenous round trip times.
Postscript |
Slides (Postscript)
An H-infinity based robust controller is designed for a rate-feedback
flow-control problem in single-bottleneck data-communication
networks. The controller is robust to uncertain time-varying
multiple time-delays in different channels. The controller forces
the queue length at the bottleneck node to the desired
steady-state value asymptotically and also satisfies a
weighted fairness condition. Some simulations are also presented to
demonstrate the time domain performance of the controller.
In a recent work by the authors, an H-infinity based flow controller
was designed for explicit rate-based congestion control in high-speed
networks. Time-daly uncertainties were taken into account when the
controller was designed. This paper studies robustness margins, e.g.,
largest allowable time delay, as functions of a weighting parameter
used in the definition of the H-infinity optimization problem. Another
issue discussed here is "non-fragile" (i.e. internally robust)
implementation of the H-infinity controller. Time-domain performance
is demonstrated via simulations.
Typical congestion control algorithms for high speed networks inclide
local flow controllers at the bottleneck nodes. In this paper an
H-infinity based controlled is developed for rate feedback in a single
bottleneck network. The rates can be assigned to the sources only
after a certain transmission delay. Controller design specifications
for this time delay system include "fairness" to multiple users,
"usage" optimization, and minimization of the transients in the queue
length. STability robustness, against uncertainties in time delays, is
also specified as a design goal. By a simple algebra the problem is
transformed to an H-infinity control of a plant with a time delay, and
it is solved by using an algorithm developed earlier for this class of
problems
Postscript (459496 bytes) |
PKzip Compressed Postscript
(97220 bytes) |
PDF
The capacity of ad hoc wireless networks is constrained by the
interference between concurrent transmissions from neighboring
nodes. Gupta and Kumar have shown that the capacity of an ad hoc
network does not scale well with the increasing number of nodes in
the system when using omnidirectional antennas.
We investigate the capacity of ad hoc wireless networks using
directional antennas. In this work, we consider arbitrary networks
and random networks where nodes are assumed to be static.
The capacity of ad hoc wireless networks is constrained by the
interference between concurrent transmissions from neighboring
nodes. Gupta and Kumar have shown that the capacity of an ad hoc
network does not scale well with the increasing number of nodes in
the system when using omnidirectional antennas.
We investigate the capacity of ad hoc wireless networks using
directional antennas. In this work, we consider arbitrary networks
and random networks where nodes are assumed to be static.
A key factor deciding the performance of a routing protocol in
mobile ad hoc networks is the manner in which it adapts to route changes
caused by mobility. Exploiting the intuition that a {\em less} dynamic
route lasts longer, we propose a new metric, the {\em Route Fragility
Coefficient} (RFC), to compare routes. RFC estimates the rate at which a
given route {\em expands} or {\em contracts}. Expansion refers to adjacent
nodes moving apart, while contraction refers to their moving closer. RFC
combines the individual link contraction or expansion behavior to present
a unified picture of the route dynamics. We demonstrate that lower the
value of RFC, more static (less fragile) the route. We then use this
metric as a basis for route selection so that route discovery yields
routes that last longer and hence increase throughput while reducing
control overhead.
We provide a simple distributed mechanism to compute RFC, so that a
Route-Request (RREQ) packet contains the metric for the path it traversed,
when it reaches the destination. The Dynamic Source Routing Protocol (DSR)
is enhanced with the proposed metric in the NS-2 simulation environment.
Simulation results are provided to demonstrate improvement in throughput
and reduction in routing protocol overhead with increased mobility.
Routing in ad-hoc sensor networks is a complicated task because of many reasons. The nodes are low powered and they cannot maintain routing tables large enough for well-known routing protocols. Because of that, greedy forwarding at intermediate nodes is desirable in ad-hoc networks. Also, for traffic engineering, multipath capabilities are important. So, it is desirable to define routes at the source like in Source Based Routing (SBR) while performing greedy forwarding at intermediate nodes.
We investigate Trajectory-Based Routing (TBR) which was proposed as a middle-ground between SBR and greedy forwarding techniques. In TBR, source encodes trajectory to be traversed and embeds it into each packet. Upon the arrival of each packet, intermediate nodes decode the trajectory and employ greedy forwarding techniques such that the packet follows its trajectory as much as possible.
In this paper, we provide techniques to efficiently forward packets along a trajectory defined as a parametric curve. We use the well-known Bezier parametric curve for encoding trajectories into packets at source. Based on this trajectory encoding, we develop and evaluate various greedy forwarding algorithms.
We analyze TCP performance in asymmetric networks, where the
throughput significantly depends on the reverse direction and packet
loss. We introduce a new operational model called the "AMP model"
which, with an understanding of TCP dynamics and buffer management
techniques explains the performance effects seen. We apply this model
to guide design improvements in buffer management (ack-regulation) and
scheduling schemes to achieve performance improvements of an order of
magnitude or more. The schemes have been tested through simulation and
implementation, and the module driven improvements observed are better
than those proposed in earlier literature.
Papers @
OSU
B. Sikdar, S. Kalyanaraman and K. S. Vastola, "Analytic Models for the
Latency and Steady-State Throughput of TCP Tahoe, Reno and SACK,"
Proceedings of IEEE Globecom, 2001.
B. Sikdar, S. Kalyanaraman and K. S. Vastola, "TCP Reno with Random
losses: Latency, Throughput and Sensitivity Analysis," Proceedings of
IEEE IPCCC, pp. 188-195, Phoenix, AZ, April 2001.
B. Sikdar, S. Kalyanaraman and K. S. Vastola, "An Integrated Model
for the Latency and Steady State Throughput of TCP Connections",
Proceedings of IFIP Symposium on Advanced Performance Modeling,
Orlando, FL, USA, Nov. 2000.
An expanded version of the above paper will appeared in Performance
Evaluation Journal (see below)
B. Sikdar, S. Kalayanaraman and K. S. Vastola, ``An integrated model for
the latency and steady state throughput of TCP connections,'' Performance
Evaluation, vol. 46, no. 2-3, pp. 139-154, September 2001.
GZIPPED Postscript
Shrikrishna Karandikar, Shivkumar Kalyanaraman, Prasad Bagal, Bob
Packer, ``TCP Rate Control,'' Computer Communications
Review, Vol 30, No 1, January 2000, pp. 45-58.
D. Shekhar, H. Qin, S. Kalyanaraman, K. Kidambi, ``Performance
Optimization of TCP/IP over Asymmetric Wired and Wireless Links,''
Invited paper at European Wireless 2002, February 2002.
Ramakrishna Satyavolu, Ketan Duvedi, Shivkumar Kalyanaraman,
"Explicit rate control of TCP applications," ATM_Forum/98-0152R1, February 1998.
gzip Compressed Postscript (255KB) |
Text (without figures) (46KB)
Slides in HTML (35KB)
Expanded Tech Report:
Postscript
Multimedia Issues/Multicast Congestion
Control/Peer-to-Peer:
Related Papers
Back to Top
Ivan V. Bajic, Omesh Tickoo, Anand Balan, Shivkumar Kalyanaraman, and John
W. Woods, "Integrated end-to-end buffer management and congestion control
for scalable video communications," IEEE ICIP'03, Barcelona, Spain,
September 2003.
Jiang Li, Shivkumar Kalyanaraman, ``Generalized Multicast Congestion
Control,'' Proceedings of 5th COST 264 International Workshop on
Network Group Communications (NGC 2003) and ICQT, Munich, Germany,
September 2003. Proceedings reprinted in Springer Lecture Notes in
Computer Science (LNCS), LNCS-2816, 2003.
Yufeng Shan and Shivkumar Kalyanaraman "Overlay Multi-hop FEC scheme for
Point-to-Point Video Streaming over Peer-to-Peer Networks", submitted, 2003.
Yufeng Shan and Shivkumar Kalyanaraman "Hybrid Video Downloading/Streaming Over Peer-to-Peer Networks",
International Conference on Multimedia and
Expo (ICME), Vol II, pp 665 - 668, Baltimore, MD, July 2003
Anand Balan, Omesh Tickoo, Ivan Bajic, Shivkumar Kalyanaraman, John
Woods, ``Integrated Buffer Management and Congestion
Control for Video Streaming,'' submitted for publication, 2002.
Jiang Li, ``End-to-End Multicast Congestion Control and Avoidance,''
Ph.D. Dissertation, August 2003.
Jiang Li, Shivkumar Kalyanaraman, ``Using Average Attenuation Factor
to Locate the Most Congested Path for Multicast Congestion Control,''
submitted, 2003.
Jiang Li, Shivkumar Kalyanaraman, ``ORMCC : A Simple And Effective
Single-Rate Multicast Congestion Control Scheme,'' submitted work,
2002.
Jiang Li, Shivkumar Kalyanaraman, ``MCA: An End-to-end Multicast
Congestion Avoidance Scheme with Feedback Suppression,'' submitted to
Journal of Computer Communications, 2002.
Jiang Li, Shivkumar Kalyanaraman, ``MCA: A Rate-based End-to-end
Multicast Congestion Avoidance Scheme,'' Proceedings of IEEE
International Communications Conference (ICC'2002), New York, NY,
April 2002.
Puneet Thapliyal, Sidhartha, Jiang Li, Shivkumar Kalyanaraman, ``LE-SBCC:
Loss-Event oriented Source-based Multicast
Congestion Control,'' Multimedia Tools and Applications Journal,
Kluwer Academic Publishers, Vol. 17, No. 2/3, 2002.
Neelkanth Natu, Priya Rajagopal, Shivkumar Kalyanaraman, ``GSC: A
Generic Source-based Congestion Control Algorithm for Reliable
Multicast,'' Journal of Computer Communications, Vol
24, No. 5-6, March 15th 2001, pp. 575-589.
Puneet Thapliyal, Sidhartha, Shivkumar Kalyanaraman, ``Source Based
Multicast Congestion Control,'' NGC'2000, Stanford, CA, November
2000 (Poster)
Network Management:
Back to Top
Hema Tahilramani Kaur, Shiv Kalyanaraman, Andreas Weiss, Shifalika
Kanwar, Ayesha Gandhi, ``BANANAS: An Evolutionary Framework for Explicit and Multipath
Routing in the Internet,'' SIGCOMM Future Directions on Network Architectures (FDNA) Workshop,
Karlsruhe, Germany, August 2003.
Garrett Yaun, Christopher D. Carothers, and Shivkumar Kalyanaraman,
"Large-Scale TCP Models Using Optimistic Parallel Simulation", In
Proceedings of the 17th Workshop on Parallel and Distributed Simulation
(PADS '03). Awarded the BEST PAPER in PADS'03.
David Bauer, Garrett R. Yaun, Christopher D. Carothers, Murat
Yuksel, Shivkumar Kalyanaraman, "A Platform for Large-Scale Network
Performance Analysis", submitted, 2003.
David Bauer, Garrett R. Yaun, Christopher D. Carothers, Murat
Yuksel, Shivkumar Kalyanaraman, "ROSS.Net: Optimistic Parallel
Simulation Framework for Large-Scale Internet Models", To appear
in the Proceedings of Winter Simulation Conference (WSC), 2003.
T. Ye, S. Kalyanaraman, ``A Unified Search Framework for Large-scale
Black-box Optimization,'' Submitted for publication.
Garrett R. Yaun, Harshad L. Bhutada, Christopher D. Carothers, Murat
Yuksel, Shivkumar Kalyanaraman, "Large-Scale Network Simulation
Techniques: Examples of TCP and OSPF Models", submitted to Computer
Communication Review, 2003.
T. Ye, S. Kalyanaraman, ``A Recursive Random Search Algorithm for
Large-Scale Network Parameter Configuration,'' To Appear in
SIGMETRICS'2003, San Diego, California, June 2003.
Tao Ye, Hema Tahilramani Kaur, Shiv Kalyanaraman, ''Large-Scale
Network Parameter Configuration Using An On-line Simulation
Framework,'' Submitted to IEEE/ACM Transactions of Networking, 2003.
Tao Ye, Shivkumar Kalyanaraman,
``A Recursive Random Search Algorithm for Black-box Optimization,''
Submitted to Journal of Global Optimization, 2003.
Debashis Basak , Hema Tahilramani Kaur, Shivkumar Kalyanaraman,
``Traffic Engineering Techniques and Algorithms for the Internet,''
RPI Technical Report, 2002.
Tao Ye, Hema Tahilramani Kaur, Shivkumar Kalyanaraman,
Kenneth S. Vastola and Saroj Yadav,
"Optimization of OSPF Weights Using On-line Simulation", submitted, 2002.
Tao Ye, Shivkumar Kalyanaraman,
``Adaptive Tuning of RED Using On-line Simulation,'' Proceedings of IEEE
GLOBECOM'2002, Taipei, Taiwan, November 2002.
Y.Tao, D. Harrison, B.Sikdar, H. Tahilramani, B.Mo, J.Jiang, S. Kalyanaraman,
B. Szymanski, and K. Vastola, ``Network Management and Control using
Collaborative On-Line Simulation,'' IEEE International Communications
Conference (ICC'2001), Helsinki, Finland, June 2001.
Pricing:
Related Papers
Back to Top
Murat Yuksel, "Architectures for Congestion-Sensitive Pricing of
Network Services," PhD Thesis, CS Department, Rensselaer Polytechnic
Institute, 2002.
Murat Yuksel, Shivkumar Kalyanaraman, "Distributed Dynamic Capacity
Contracting: An overlay congestion pricing framework", To appear in
Journal of Computer Communications, 2003.
Murat Yuksel, Shivkumar Kalyanaraman
"Distributed Dynamic Capacity Contracting: A congestion pricing
framework for Diff-Serv," Proceedings of IFIP/IEEE International
Conference on Management of Multimedia Networks and Services (MMNS),
Santa Barbara, CA, October 2002.
Mehdi Aboulfadl, Ritesh Pradhan, Aparna Gupta, and, Shivkumar
Kalyanaraman, "A Spot Pricing Framework To Enable Pricing And Risk
Management Of Inter-Domain Assured Bandwidth Services", To appear in
Proceedings of Winter Simulation Conference, San Diego, 2002.
Murat Yuksel, Shivkumar Kalyanaraman, Anuj Goel, "Congestion Pricing
Overlaid on Edge-to-Edge Congestion Control", Proceedings of ICC 2003,
Anchorage, AK, May, 2003.
Murat Yuksel, Shivkumar Kalyanaraman
"Elasticity Considerations for Optimal Pricing of Networks", Proceedings of IEEE International Symposium on Computer
Communications (ISCC), Antalya, Turkey, July 2003.
Murat Yuksel, Shivkumar Kalyanaraman "Pricing Granularity for
Congestion-Sensitive Pricing",
Proceedings of IEEE International Symposium on Computer Communications
(ISCC), Antalya, Turkey, July 2003.
Murat Yuksel, Shivkumar Kalyanaraman "A Strategy for Implementing
Smart Market Pricing Scheme on Diff-Serv," Proceedings of
GLOBECOM, 2002, Taipei, Taiwan, Nov 2002.
Gurjeet S. Arora, Murat Yuksel, Shivkumar
Kalyanaraman, Thiagarajan Ravichandran, Aparna Gupta,
"Price Discovery at Network Edges," Proceedings of
International Symposium on Performance Evaluation of Computer and
Telecommunication Systems (SPECTS), July 2002.
Murat Yuksel, Shivkumar Kalyanaraman,
"Simulating the Smart Market Pricing Scheme on Differentiated-Services
Architecture," Communication Networks and Distributed Systems Modeling
and Simulation Conference (CNDS part of Western MultiConference),
Phoenix, AZ, 2001.
Ranjeeta Sinha, Murat Yuksel, Shivkumar Kalyanaraman, T. Ravichandran,
"A Comparative Evaluation of Internet Pricing Models: Smart Markets
and Dynamic Capacity Contracting," The 10th Workshop on Information
Technologies and Systems (WITS'2000), Brisbane, Australia, December
2000.
Differentiated
Services/TCP-Friendly Marker Work:
Related Papers
Back to Top
S. Raghunath, S. Kalyanaraman, "Statistical Point-to-Set Edge-based
Quality of Service Assurances", QoFIS 2003, Stockholm, Sweden, October 2003.
Satish Raghunath, "Edge-based Services for Quality of Service
Guarantees in the Internet", PhD Candidacy Document, ECSE Department,
Rensselaer Polytechnic Institute, 2003.
The challenges facing QoS provisioning in the next generation Internet
involve building simple solutions to provide a priori assurances while
being able to exploit statistical multiplexing gains. In this thesis we
consider two important aspects of this problem: a) Expanding the scope of
QoS beyond point-to-point assurances to point-to-multipoint services; b)
Decoupling the computation of QoS assurances from instantaneous traffic
characteristics.
Traditional QoS models have concentrated on point-to-point models.
However, customer networks frequently need assurances toward multiple
destination sites. By expanding the spatial granularity of QoS assurances,
we eliminate the need to provision point-to-point links for each
source-destination pair while still providing statistical assurances on
QoS. Since our architecture is completely edge-based, it is easily
deployed without any changes to the network core. In order to provide a
priori assurances with such an edge-based architecture we build an
analytical framework that allows us to compute QoS metrics without needing
to know the exact nature of number of the flows in the system. Thus our
framework allows computing QoS assurances given just a topology and
routing scheme.
The highpoint of the proposed architecture is the simple edge-based
admission control algorithm that is evolved to achieve these goals. By
introducing simple constraints on the leaky-bucket parameters of the flows
admitted into the system, we demonstrate that bounds on edge-to-edge delay
can be obtained. In summary, the contribution of this thesis in building a
new edge-based architecture providing {\em a priori} QoS assurances with
an enhanced spatial granularity.
Satish Raghunath, Kartikeya Chandrayana, Shivkumar Kalyanaraman,
``Edge-Based QoS Provisioning for Point-to-Set Assured Services,''
ICC 2002, New York NY
G.L. Monoco, F. Azeem, S. Kalyanaraman, Y.Xia, ``TCP-Friendly Marking for
Scalable Best-Effort Services on the Internet,'' Computer
Communication Review (CCR), Volume 31, Number 5, October 2001.
F. Azeem, A. Rao, S. Kalyanaraman, ``A TCP-Friendly Traffic Marker for
IP Differentiated Services,'' IwQoS'2000, Pittsburg, PA,
June 2000.
Related IETF Internet Draft:
draft-azeem-tcpfriendly-diffserv-00.txt :
In Text
S. Kalyanaraman, D. Harrison, S. Arora, K. Wanglee, G. Guarriello, "A
one-bit feedback enhanced differentiated services architecture,"
Internet Draft, draft-shivkuma-ecn-diffserv-00.txt, March 1998.
Control-theoretic Work:
Related Papers
Back to Top
P.F. Quet, B. Ataslar, A. Iftar, H. Ozbay, T.Kang, S. Kalyanaraman,
``Robust Rate-Based
Controllers for High Speed Networks: The Case of Uncertain
Time-varying Multiple Time delays,'' Automatica Journal,
Vol. 38, 2002, pp. 917-928.
P.F. Quet, S. Ramakrishnan, H. Ozbay, S. Kalyanaraman,
``On the H-infinity Controller Design for Congestion Control
with a Capacity Predictor,'' Proceedings of the Conference on
Decision and Control (CDC), December 2001, Orlando FL.
Sthanunathan Ramakrishnan, Shivkumar Kalyanaraman, John Wen, Hitay
Ozbay, ``Effect of Time Delay in Network Traffic Control,'' Short
Paper, Automatic Controls Conference (ACC), 2001.
A. Iftar, H. Ozbay, T.Kang, S. Kalyanaraman, ``Robust Rate-Based
Controllers for High Speed Networks: The Case of Uncertain
Time-varying Time delays,'' Proceedings of Automatic Controls Conference
(ACC), 2000.
H. Ozbay, T. Kang, S. Kalyanaraman, A. Iftar, ``Performance and
Robustness Analysis of an H-infinity based Flow Controller,''
Proceedings of the Conference on Decision and Control (CDC),
Phoenix, AZ, December 1999.
Hitay Ozbay, Shivkumar Kalyanaraman, Altug Iftar,
"On Rate-Based Congestion Control in High Speed Networks: Design of an
H-infinity Based Flow Controller for Single Bottleneck" American
Control Conference, July 1997.
Wireless Work:
Back to Top
Su Yi, Yong Pei, Shivkumar Kalyanaraman, and Babak Azimi-Sadjadi, "How
is the Capacity of Ad Hoc Networks Improved with Directional
Antennas?" Submitted to IEEE Journal on Selected Areas in
Communications issue on Fundamental Performance Limits of Wireless
Sensor Networks, 2003
In arbitrary networks, due to the reduction of the interference
area and the reduced probability of two neighbors pointing to each
other, the capacity is proven to achieve a gain in terms of the
antenna beamwidth and depending on the different antenna modes in
transmission and reception. We also state that the per-node
capacity would achieve constant with the increase of number of
nodes when some requirements are met for antenna beamwidth and
transmission range. For random networks, interfering neighbors are
reduced due to the decrease of interference area when directional
antennas are used for transmission and/or reception. Thus
throughput capacity of the networks will be improved by using
directional antennas. We have also analyzed hybrid beamform
patterns that are a mix of omnidirectional/directional and a
better model of real directional antennas.
Su Yi, Yong Pei, and Shivkumar Kalyanaraman, "On the Capacity
Improvement of Ad Hoc Wireless Networks Using Directional Antennas",
ACM Mobihoc 2003, Annapolis, MD, June 2003.
In arbitrary networks, due to the reduction of the interference
area, the capacity gain is proven to be
$\sqrt{\frac{2\pi}{\alpha}}$ when using directional transmission
and omni reception. Because of the reduced probability of two
neighbors pointing to each other, the capacity gain is
$\sqrt{\frac{2\pi}{\beta}}$ when omni transmission and directional
reception are used. Although these two expressions look similar,
the proof technique is different and new. By taking advantage of
the above two approaches, the capacity gain is
$\frac{2\pi}{\sqrt{\alpha\beta}}$ for the case both transmission
and reception are directional.
For random networks, interfering neighbors are reduced due to the
decrease of interference area when directional antennas are used
for transmission and/or reception. The throughput improvement
factor is $\frac{2\pi}{\alpha}$, $\frac{2\pi}{\beta}$ and
$\frac{4\pi^2}{\alpha\beta}$ for directional transmission/omni
reception, omni transmission/directional reception, and
directional transmission/directional reception, respectively.
We have also analyzed hybrid beamform patterns that are a mix of
omnidirectional/directional and a better model of real directional
antennas.
O.Tickoo, S. Raghunath, S. Kalyanaraman, "Route Fragility: A
Novel Metric for Route Selection in Mobile Ad Hoc Networks", IEEE ICON
2003, Sydney, Australia.
Murat Yuksel, Ritesh Pradhan, Shivkumar Kalyanaraman, "Trajectory-Based
Forwarding Mechanisms for Ad-Hoc Sensor Networks" (Extended Abstract), To appear in IEEE 2nd Upstate Workshop on Sensor Networks, Syracuse, NY, October, 2002.
D. Shekhar, H. Qin, S. Kalyanaraman, K. Kidambi, ``Performance
Optimization of TCP/IP over Asymmetric Wired and Wireless Links,''
Invited paper at European Wireless 2002, February 2002.
Back to All Publications
Back to Shivkumar Kalyanaraman's home page