There have been many studies for modeling vehicular traffic flow using fluid models. However, these previous approaches do not accommodate realistic models for traffic density, flow, and velocity. The existing models also fail to uncover the relationships among energy efficiency, capacity, and safety. We investigate traffic networks from a system-level perspective. In result, we provide a time-gap based mathematical traffic model for vehicular traffic flow on highways. Our model explains the widely known triangular fundamental diagram, which represents vehicular traffic systems with the three primary parameters: maximum free-flow velocity, a typical safety length of vehicles, and a mean value of the time-gap of the traffic data during congested conditions. This result is also well validated with measured traffic data using least squares matching and with previous research outcomes about the propagation velocity. In addition, we suggest two distinct analysis techniques to estimate the time-gap from the traffic data measured on highways.

We investigate opportunistic multicast scheduling schemes for sending a multicast stream in a wireless cell. We propose schemes that exploit both multiuser diversity and broadcast gains for efficient multicast, preserve the feature of synchronization of served information provided by conventional multicasting, and provide for receivers accepting sequential stream data. With knowledge of the expected sequence number (SN) of stream data and the feasible peak transmission rate for each group member, our scheme decouples the pairing of SN and rate and selects an expected SN and a peak rate that jointly maximize a utility function. Besides the amount of data accepted in one transmission, the function includes a force factor to push expected SNs to drift closely and another force factor to synchronize more expected SNs. Under i.i.d. channel conditions, we show that with the two factors to limit the diffusion of expected SNs, multicast throughput significantly increases and that without them our scheme degenerates into merely tapping multiuser diversity gain. Furthermore, we investigate optimal transmit power allocation subject to an average power constraint for multicast transmission. Results show that multicast throughput increases slightly for our scheme but substantially for traditional ones.

In this paper, we consider a time-slotted MIMO point-to-multipoint network, which, for example, could represent either a cellular downlink, or a cluster in a wireless mesh network. The transmitter sends an independent data stream from each transmit antenna to communicate simultaneously to a subset of the receivers in each slot. The transmitter sends training symbols at the beginning of each slot so that each receiver can estimate the channel and determine the data rate it could potentially receive from each transmit antenna after configuring its antenna weights appropriately. For this purpose, we develop a maximum-likelihood estimator of the signal to interference plus noise ratio (SINR) from the received training symbols. The transmitter decides which receivers to serve in each slot to maximize the minimum normalized average data rate realized by each receiver. This scheduling decision is made based on estimated SINR information fed back by receivers. Through some numerical examples, we discuss some general issues with regard to exploitation of multi-user diversity in the context of imperfect channel state information. For example, the scheduler introduces a bias for positive SINR estimation errors, which is important to take into account when the receivers declare a potential data rate in each slot.

We find the exact per-node capacity scaling in an extended, distributed wireless network where the node locations are random, the channel attenuation between pairs of nodes exhibits independent random fading, and data forwarding is restricted to multihop delivery. We establish a per-node throughput upper bound equal to (Cmax)/(radicn) (bps)/(Hz), and a constructive lower bound equal to (Cmin)/(radicn) (bps)/(Hz), where Cmaxand Cminare constants andnis the expected number of nodes in the network. The results apply with probability approaching unity asnbecomes large, under independent, frequency flat, fading channel conditions where the tail probability exhibits an exponential decay (e.g., any mixture of line-of-sight and Rayleigh, Rice and Nakagami distributions). Our lower bound is mainly motivated by a clever bond-percolation-based protocol construction, introduced by Franceschetti et al., where it was shown that a per-node throughput equal to a constant times 1/(radicn) (bps)/(Hz) is achievable in networks with random node locations under a deterministic channel gain modeling path-loss and absorption. We extend the result to more realistic channel gain models in which the channel gains are modeled as random due to multipath effects. The protocol systematically leverages multiuser diversity to overcome the added uncertainty. The key to the upper bound is to establish an upper bound for the total network transport capacity. This upper bound proves that, relative to the lower bound construction, any attempt to leverage multiuser diversity further will result in no more than a constant factor of throughput gain.

This paper explores the use of rate adaptation in cellular networks to maximize throughput of long-lived TCP sessions. We focus on the problem of maximizing the throughput of TCP connections and propose a joint optimization of MAC and physical layer parameters with respect to TCP sending rate. In particular, we propose a simple TCP-aware channel scheduler that adapts the wireless channel rate to changes in the TCP sending rate and explore its performance for both single and multiple concurrent sessions. In the case of a single TCP session, we develop a fluid model of its steady-state behavior in such a system that adapts between two channel rates. Our results indicate that a two-rate scheme improves TCP throughput by 15% to 20% over a system that does not exploit rate adaptation and that little additional benefit accrues from the addition of a third channel rate. Finally, we extend the framework to scenarios where bandwidth is shared by multiple TCP sessions. We propose two channel allocation algorithms and explore their performance through simulation. Our results indicate that TCP throughput is relatively insensitive to either channel allocation algorithm and adaptive rate variation is the dominant factor in performance.

In this paper, we propose packet size aware path setup mechanisms for 802.11 based multi-hop WLAN networks. Path setup optimization is achieved by minimizing the transmission delay experienced by each packet traversing from source to the destination where different packets belonging to the same source destination pair can traverse different paths based on their sizes. We implemented a sample packet size aware path setup scheme as a Linux kernel module and experimentally showed the benefits of such a scheme in terms of the transmission delay and the throughput in an 802.11b WLAN environment. In addition to that we examine general path setup solutions for wireless networks considering packet size statistics.

In this paper, we consider the joint beamforming, power control and scheduling problem in a multiple-input single- output (MISO) downlink for maximizing the minimum weighted rate among all users. We solve this problem by formulating it as a convex optimization problem whose function evaluations require maximization of a difference of convex functions (D.C. Programming). We also propose a simpler heuristic that finds the best policy under restricted set of power vectors. We then compare the performance of these policies against the dirty paper coding (DPC) policy to quantify the performance gap between an optimal point-to-point coding approach and an optimal joint encoding/decoding approach.

In this paper we study optimal transmission strategies in wireless ad-hoc networks using directional antennas. Each node is capable of adjusting its transmission rate as well as its transmission and reception beam-widths. We explore the different tradeoffs involved in optimizing the performance. Specifically we look at the problem of optimally allocating the transmission rate given specific transmission and reception beam-widths. We then use those results to find the optimum beam-widths for maximizing the average throughput-distance. We illustrate this two stage optimization algorithm by numerical examples. We show that even when the transmission rate is chosen optimally, a bad choice of beam-width can degrade the performance by over 50%.

In this paper, we analyze the impact of imperfect channel quality feedback on the scheduling algorithms that exploit multi-user diversity. We consider a time-slotted MIMO broadcast network where the transmitter uses its multiple antennas for spatial multiplexing to communicate simultaneously to a subset of the receivers in each slot. The transmitter sends training symbols at the beginning of a slot so that each receiver can estimate the data rate it could potentially receive from each transmit antenna. For this purpose, we develop a maximum-likelihood estimator (MLE) of SINR. The receivers report the rate information, which is noisy due to estimation errors, to the transmitter to assist its scheduling decisions. Through numerical examples, we discuss some general issues regarding exploitation of multi-user diversity with imperfect channel state information. For example, the scheduler introduces a bias for positive SINR estimation errors, which is important to take into account when the receivers declare a potential data rate in each slot.

Enterprise networks are increasingly offloading the responsibility for worm detection and containment to the carrier networks. However, current approaches to the zero-day worm detection problem such as those based on content similarity of packet payloads are not scalable to the carrier link speeds (OC-48 and up-wards). In this paper, we introduce a new system, namely DoWitcher, which in contrast to previous approaches is scalable as well as able to detect the stealthiest worms that employ low-propagation rates or polymorphisms to evade detection. DoWitcher uses an incremental approach toward worm detection: First, it examines the layer-4 traffic features to discern the presence of a worm anomaly; Next, it determines a flow-filter mask that can be applied to isolate the suspect worm flows and; Finally, it enables full-packet capture of only those flows that match the mask, which are then processed by a longest common subsequence algorithm to extract the worm content signature. Via a proof-of-concept implementation on a commercially available network analyzer processing raw packets from an OC-48 link, we demonstrate the capability of DoWitcher to detect low-rate worms and extract signatures for even the polymorphic worms.

To prolong the lifetime of battery powered wireless devices, standard protocols for WLANs have the provision for such devices to transition to a "sleep" state periodically. Being in the "sleep" state entails minimal power consumption by a wireless device but it also increases the average packet delay that the device encounters. This paper proposes a simple, centralized, dynamic, scalable and adaptive algorithm to optimize the duration of sleep states of wireless nodes operating in the infrastructure mode in a WLAN, with the objective of minimizing their power consumption with respect to a QoS constraint namely average packet delay. The algorithm dynamically adjusts the sleep duration of a node to its average packet arrival rate and its average packet delay constraint. The performance of this algorithm is compared with a common power saving protocol implemented in WLANs like 802.11, namely, a static sleep mechanism where the sleep duration of a devise is set to be equal to the average delay constraint of the devise. Simulation results prove the power efficiency of the adaptive sleep algorithm over the static sleep scheme especially for non uniform traffic.

For any multiple-input multiple-output (MIMO) network with linear beamformers, it is shown that there exists a dual network that attains the same signal-to-interference-plus-noise ratio (SINR) performance. This network duality concept is a generalization of the virtual uplink concept investigated by Rashid-Farrokhi . We first develop the dual relation using a generic duality theory in linear programming. This approach naturally leads to the construction of a dual network, and provides machinery for handling a generalized cost function. We then consider the joint MIMO beamforming and power control problem with individual SINR constraints. We apply the network duality to this problem and propose a high-performance iterative algorithm which, compared with past centralized approaches, has improved convergence behavior. Finally, we propose a simpler distributed version of the algorithm tailored for a cellular downlink. This algorithm can be readily implemented in a distributed fashion, since it does not require information exchange between base stations. The algorithm achieves performance close to that of centralized ones, and outperforms other decentralized approaches available in the literature

In this paper, the problem of end-to-end weighted max-min fair rate assignment in a two-channel multi-hop CDMA wireless access network is discussed. We show that end-to-end endweighted global max-min fairness (hierarchical as well as flow-based) can be achieved by simple extension of mac-layer fairness. In particular, we show that weighted end-to-end flow-based as well as hierarchical global max-min fairness can be simply insured if and only if weighted mac-layer max-min and weighted transport-layer max-min fair rates are achieved. The same results can easily be shown to be valid for more general wireless networks, which will be briefly discussed in this paper as well. In addition, we discuss a mac-layer algorithm, MAC-α G algorithm, that, with careful choice of parameters, not only provides weighted α-proportional fairness at the mac layer, but also leads to end-to-end weighted global max-min fairness (both flow-based and hierarchical) with an appropriate higher-layer protocol (i.e. weighted transport-layer max-min fair protocol).

TCP is the dominant transport protocol over both wired and wireless links. It is however, well known that TCP is not suitable for wireless networks and several solutions have been proposed to rectify this shortcoming. In this work, we explore cross-layer optimization of the rate adaptation feature of cellular networks to optimize throughput of a single long-lived TCP session. Modern cellular networks rate RF technology that allows them to dynamically vary the wireless channel rate in response to user demand and channel conditions. However, the set of data rates as well as the scheduler's rate adaptation policy are typically chosen to optimize throughput for inelastic applications. In order to optimize such a system for TCP, we propose a two state TCP-aware scheduler that switches between two chanrates as a function of the TCP sending rate. We develop a fluid model of the steady-state behavior of a TCP session in such a system and derive analytical expressions for TCP throughput that explicitly account for rate variability as well as the dependency between the scheduler and TCP. Using the model we choose RF layer parameters that, in conjunction with the TCP-aware scheduler, improve term throughput of a single TCP flow by 15.25%. We also compare our analytical results against those obtained from ns-2 simulations and confirm that our model indeed closely approximates TCP behavior in such an environment.

In this paper, we propose a simple analytic model for a physical carrier sensing wireless ad-hoc network. Attempted packet transmissions are modeled as a three dimensional Poisson point process in space and time. Each node measures the total interference power before an attempted transmission, and proceeds with the transmission only if the total interference power is below a threshold, called the idle threshold. A completed transmission is successfully received if the interference power at the intended destination is suitably low during the transmission. The total interference process is modeled as a shot noise that is a filtered in space and time, which accounts for an infinite number of concurrent transmissions on the infinite plane. We make a Gaussian approximation for the power of the interference process. A key mechanism for physical carrier sensing we take into account in our model is the inhibitory effect of nearby neighbors around an existing transmission. The inhibiting model is based on the threshold on the interference level rather than a geographically defined region. We model this effect using the conditional intensity of transmissions given an existing transmission, which can be solved using a system of two fixed point equations. We further approximate the conditional statistics of transmissions as Poisson to obtain a simpler model. We compare the predictions using the simpler model to Monte Carlo simulations results based on the model without the Poisson approximation, and we find a reasonably close match. Our results suggest the simpler model can be used as a guide to set the protocol parameters such as transmission attempts intensity, distance between the transmitter and its intended receiver, transmission power, packet duration, idle and packet detection threshold, in order to optimize network throughput

A low signal to interference and noise ratio (SINR) wireless environment makes successful reception and accurate detection of packets a challenging task. We can combat a low SINR by using direct-sequence spread spectrum modulation with a sufficiently high processing gain, as well as by employing block codes for FEC on each packet. In this paper, we propose a packet detection and acquisition method for low SINR environments. The received waveform is processed using a non-linear filtering algorithm based on a maximum likelihood ratio calculation to detect the presence of transmitted packets. The algorithm uses the entire packet transmission for chip timing synchronization and code acquisition at the receiver. The performance of the algorithm is analyzed using simula- tions and real packet transmissions captured over the wireless medium. The algorithm is finally implemented on a FPGA which is a part of a wireless transceiver prototype. The experimental results are reported.

Point-to-point delay is an important network performance measure as well as a key parameter in SLAs. We study how to measure and report delay in a concise and meaningful way for an ISP, and how to monitor it efficiently. We analyze various measurement intervals and potential metric definitions. We find that reporting high quantiles (between 0.95 and 0.99)every 10-30 minutes as the most effective way to summarize the delay in an ISP. We then propose an active probing scheme to estimate a high quantile with bounded error. We show that only a small number of probes are sufficient to provide an accurate estimate. We validate the proposed delay monitoring technique on real data collected on the Sprint IP backbone network.

For any multiple-input and multiple-output (MIMO) network with linear beamformers, there exists a dual network that attains the same signal to interference plus noise ratio (SINR) performance. This network duality is a generalization of the virtual uplink concept investigated in R. Rashid-Farrokhi et al. (1998) in the context of cellular networks. In this paper, we develop network duality which is applicable to arbitrary multi-user MIMO networks with a generalized cost function. More importantly, we provide an optimization theoretic perspective of network duality which naturally leads to the construction of a dual network. We then consider the joint MIMO beamforming and power control problem with individual SINR constraints. We apply the network duality to this problem and propose a high performance algorithm which compared to past approaches has improved convergence behavior.

Cognitive radios, MlMO antennas, wireless mesh networks, self-configuration support, seamless and context mobility, mobile user agents, and mobiquitous, multimedia, always-on, location-based communication services, are just some of the terms that have become part of the emerging lexicon to describe the future wireless communication technology landscape for 4G and beyond. From the mobile device, airlinks, and Internet access network to the applications and services that next generation mobile service providers are to support, only one point seems to enjoy global consensus: we have barely begun to scratch the surface in creating the networks to serve the communication needs of a future media-hungry world equipped with an ever-increasing number of wireless devices. At the core of all this anticipated growth lies the following question: what technology enablers or application drivers will provide the incentive to fuel all these innovations? This panel will elicit thought-provoking discussions on the evolution and/or revolution of wireless and mobile networking technology. Technology experts from academia and industry will share their perspectives on which are the key drivers that are likely to support the introduction of innovations and propose a technology roadmap highlighting research, industrial, and political challenges to be addressed. Those who can predict where the next big bang is likely to occur will have a running start in the race to untether the communication services of future generations.

We propose a new service model based on service curves, which has a loss aspect. In this model, instead of forcing all the packets to meet their deadlines assigned via a service curve, we allow some packets to be dropped. Specifically, the new model is based on guaranteeing at least a certain fraction of the all packets to meet their deadlines assigned via a service curve. The proposed model is composable. We find a necessary and sufficient condition to employ for an efficient connection admission control at a multiplexer to deliver the services according to the new model, via a graph-theoretic approach. A scheduling algorithm to deliver the services as specified by the new service model, at a multiplexer, also exists.

We show the composability of a new service model that we propose, which incorporates packet loss. The new model is based on guaranteeing at least a certain fraction of the all packets of a flow, which is to be served through a network element, to meet their deadlines assigned, via a service curve. We also propose a scheduling algorithm to deliver the services as specified by the new service model at a multiplexer. The correctness of the proposed algorithm is also shown

We consider the traffic matrix estimation problem in IP backbone networks, whose goal is to accurately estimate the volume of traffic traveling between network endpoints. Previous approaches to this problem involve measuring the volume of traffic on each link in the network during a time interval where the routing configuration is fixed, and exploit a statistical model of the traffic in order to obtain an estimate of the traffic matrix. These previous approaches are prone to large estimation errors because the link measurements from a fixed muting scenario constitute a data set that is simply too limited to provide enough data to enable estimation procedures that yield very small errors. We propose the idea of collecting link measurements under multiple routing scenarios so that the traffic matrix can be determined very accurately. We present an algorithm for determining a sequence of routing configurations, each of which is specified by a set of link weights. We incorporate carrier requirements into our algorithm so that our proposed routing configurations are operationally viable. We present the results of applying our algorithm to some representative IP backbone topologies and discuss the performance trade-offs that arise.

We compare the performance of two multiple antenna systems to be used in quality of service (QoS) supported indoor wireless networks. While a conventional array antenna system (AAS) has collocated, closely spaced antenna elements, a distributed antenna system (DAS) has largely spaced antennas over the entire area of radio coverage. To support multimedia applications requiring high bandwidth and on time delivery, we propose a set of highly spectrum efficient radio resource management algorithms. We focus on the optimization of downlink since many kinds of Internet traffic show the downlink dominance in their traffic asymmetry. To maximize the downlink throughput, we present a new transmit beamforming algorithm which can be equally applied to both DAS and AAS. The beamforming algorithm is integrated with a link scheduling algorithm that exploits the space division multiplexing (SDM) capability of multiple antenna systems to meet the QoS requirements of all terminals. Numerical examples conducted for a line of sight (LOS) environment demonstrate that a network with DAS outperforms one with AAS in terms of signal coverage and provides 40-160% higher capacity.

In a wireless network, co-channel interference among links can significantly deteriorate the performance. Power control and link scheduling provide mechanisms to manage interference. Transmission power consumption is critical to the lifetime of a wireless device. For the sake of conserving power, our goal is to manage the interference to meet the system performance requirement most efficiently. The objective is to find a transmission strategy that minimizes the power consumption while maintaining a prespecified average data rate on each link. We model the problem as a convex optimization and attempt to get a solution from its dual. Unlike previous work which assumed a linear relationship between instantaneous data rate on a link and signal to interference plus noise ratio, we use a logarithmic relation as suggested by the Shannon capacity formula. The dual problem is solved sequentially using a combination of a "difference of convex function (DC) program" and a dual computational method. We find that the optimization of power control can be decoupled from link scheduling. Any power allocation solving the dual problem is a candidate for a component of the optimal solution, and we call it a transmission mode. Our analysis shows that an appropriate time-sharing among these transmission modes, which achieves the required average data rate, is an optimal strategy. Simple numerical examples suggest that when the interference is low, the best policy is to transmit on all the links simultaneously with appropriate power control. As the interference becomes severe, the best policy is to schedule the links in a TDMA manner.

We describe an optical ring media access architecture, a media access (MAC) protocol, and a test bed implementation. The optical ring media access architecture is designed to facilitate high-speed broadband access for small business, residential, and mobile users. In our scheme, users can access a wide area network (WAN), such as the Internet, through a media access node (assumed to be a short distance away from the user). The transmission of data from the access node to the destination is done via an optical ring to a central office residing on the ring and from the central office via WAN to the destination, which may be hosted by a media access node on another optical ring. The MAC protocol is based on the earliest deadline first (EDF) scheduling to provide quality of service (QoS) for traffic flows on the ring. The test bed implementation consists of four media access nodes connected by an optical ring. Each node is implemented as a board which consists of an FPGA, an SRAM chip, optical interface modules, etc. Finally, we describe bandwidth and latency measurements showing differentiated performance for prioritized flows.

In this paper we investigate a new idea for traffic matrix estimation that makes the basic problem less under-constrained, by deliberately changing the routing to obtain additional measurements. Because all these measurements are collected over disparate time intervals, we need to establish models for each Origin-Destination (OD) pair to capture the complex behaviours of internet traffic. We model each OD pair with two components: the diurnal pattern and the fluctuation process. We provide models that incorporate the two components above, to estimate both the first and second order moments of traffic matrices. We do this for both stationary and cyclo-stationary traffic scenarios. We formalize the problem of estimating the second order moment in a way that is completely independent from the first order moment. Moreover, we can estimate the second order moment without needing any routing changes (i.e., without explicit changes to IGP link weights). We prove for the first time, that such a result holds for any realistic topology under the assumption of minimum cost routing and strictly positive link weights. We highlight how the second order moment helps the identification of the top largest OD flows carrying the most significant fraction of network traffic. We then propose a refined methodology consisting of using our variance estimator (without routing changes) to identify the top largest flows, and estimate only these flows. The benefit of this method is that it dramatically reduces the number of routing changes needed. We validate the effectiveness of our methodology and the intuitions behind it by using real aggregated sampled netflow data collected from a commercial Tier-1 backbone.

SNMP statistics are usually collected over intervals of 5 minutes and correspond to average activity of IP links and network elements for the duration of the interval. Nevertheless, reports of traffic performance across periods of minutes can mask out performance degradation due to short-lived events, such as micro-congestion episodes, that manifest themselves at smaller time scales. In this paper we perform a measurement study of packet traces collected inside the Sprint IP network to identify the time scales over which micro-congestion episodes occur. We characterize these episodes with respect to their amplitude, frequency and duration. We define a new performance metric that could be easily computed by a router and reported every 5 minutes through SNMP to shed light into the micro-behavior of the carried traffic. We show that the proposed performance metric is well suited to track the time scales over which micro-congestion episodes occur, and may be useful for a variety of network provisioning tasks.

In this paper, we study the problem of joint routing, link scheduling and power control to support high data rates for broadband wireless multihop networks. We first address the problem of finding an optimal link scheduling and power control policy that minimizes the total average transmission power in the wireless multihop network, subject to given constraints regarding the minimum average data rate per link, as well as peak transmission power constraints per node. Multiaccess signal interference is explicitly modeled. We use a duality approach whereby, as a byproduct of finding the optimal policy, we find the sensitivity of the minimal total average power with respect to the average data rate for each link. Since the minimal total average power is a convex function of the required minimum average data rates, shortest path algorithms with the link weights set to the link sensitivities can be used to guide the search for a globally optimum routing. We present a few simple examples that show our algorithm can find policies that support data rates that are not possible with conventional approaches. Moreover, we find that optimum allocations do not necessarily route traffic over minimum energy paths.

We study the problem of radio resource allocation in wireless multihop networks. The main objective is to develop integrated link scheduling and power control policies to maximize the network throughput. Transmitters in the network are subject to average power constraints per link and peak power constraints per node. Subject to these constraints, we find optimal subsets of concurrent transmitters and associated power levels to maximize network throughput, taking into account multi-access interference. We find that when ambient noise levels are sufficiently high, it is generally desirable to enable simultaneous transmissions, even if they are in close geographic proximity. We compare our results against pure CDMA to illustrate the significant gains of our approach. The results in this paper are applicable to multihop and single hop networks.

By extending the system theory under the (min, +) algebra to the time-varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic-regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t) = min[f(t+ d), f (t)+q] and the maximal f-regulator. The g-clipper is a bufferless device, which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a buffered device that delays packets as necessary in order that its output be conformant to an envelope f. The maximal f-regulator is a linear time-invariant filter with impulse response f, under the (min, +) algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, "filter bank summation," and feedback to form a composite dynamic server. We also show that dynamic service guarantees for multiple input streams sharing a work-conserving link can be achieved by a dynamic service curve earliest deadline scheduling algorithm, if an appropriate admission control is enforced.

The development of scalable service models for integrated services networks is crucial for fostering interoperability and competition among multiple network service providers that support quality of service. A key scalability property of a service model is composability, which allows models for network elements in tandem to be lumped together into a composite model which is of the same type as the constituent service models. We present a new service model for lossy network elements, and show that it is composable. To illustrate the new service model, we characterize some fundamental network elements in terms of it.

High-speed networks are expected to carry traffic classes with diverse quality of service (QoS) guarantees. For efficient utilization of resources, sophisticated scheduling protocols are needed; however, these must be implemented without sacrificing the maximum possible bandwidth. This paper presents the architecture and implementation of a self-timed real-time sorting network to be used in packet switches that support a diverse mix of traffic. The sorting network receives packets with appropriately assigned priorities and schedules the packets for departure in a highest-priority-first manner. The circuit implementation uses zero-overhead, self-timed, and self-precharging domino logic to minimize the circuit latency. An experimental sorting network chip has been designed using the techniques described in this paper to support 10 Gb/s links with ATM-size packets.

By extending the filtering theory under the (min, +)-algebra to the time varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t)=min[f(t+d), f(t)+q] and the maximal f-regulator. The g-clipper is a bufferless device which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a buffered device that delays packets as necessary in order that its output be conformant to an envelope f. The f-regulator is a linear time invariant filter with impulse response f, under the (min, +)-algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, "filter bank summation" and feedback to form a composite dynamic server, we also show that dynamic service guarantees for multiple input streams sharing a work conserving link can be achieved by a dynamic SCED (service curve earliest deadline) scheduling algorithm, if an appropriate admission control is enforced.

We discuss a simple conceptual framework for analyzing the flow of data in integrated services networks. The framework allows us to easily model and analyze the behavior of open loop, rate based flow control protocols, as well as closed loop, window based flow control protocols. Central to the framework is the concept of a service curve element, whose departure process is bounded between the convolution of the arrival process with a minimum service curve and the convolution of the arrival process with a maximum service curve. Service curve elements can model links, propagation delays, schedulers, regulators, and window based throttles. The mathematical properties of convolution allow us to easily analyze complex configurations of service curve elements to obtain bounds on the end-to-end performance. We demonstrate this by examples, and investigate tradeoffs between buffering requirements, throughput, and delay, for different flow control strategies.

We introduce a new scheduling policy which provides guaranteed service for a session based on a flexible service specification called the service curve. This policy, referred to as the service curve based earliest deadline first policy (SCED), is a generalized policy to which well-known policies such as virtual clock and the earliest deadline first (EDF) can be mapped as special cases, by appropriate specification of the service curves. Rather than characterizing service by a single number, such as minimum bandwidth or maximum delay, service curves provide a wide spectrum of service characterization by specifying the service using a function. The flexibility in service specification allows a user, or the network, to specify a service that best matches the quality-of-service required by the user, preventing an over-allocation of network resources to the user. For a single server, we show that the SCED policy is optimal in the sense of supporting the largest possible schedulability region, given a set of delay-bound requirements and traffic burstiness specifications. For the case of a network of servers, we show that the SCED policy has a greater capability to support end-to-end delay-bound requirements than other known scheduling policies. The key to this capability is the ability of SCED to allocate and guarantee service curves with arbitrary shapes.

High speed networks are expected to carry traffic classes with diverse Quality of Service (QoS) guarantees. For efficient utilization of resources, sophisticated scheduling protocols are needed; however; these must be implemented without sacrificing the maximum possible bandwidth. This paper presents the architecture and implementation of a self-timed real-time sorting network to be used in packet switches that support a diverse mix of traffic. The sorting network receives packets with appropriately assigned priorities, and schedules the packets for departure in a highest-priority-first manner. The circuit implementation uses zero-overhead, self-timed, self-precharging domino logic and timed-roadblock techniques to minimize the circuit latency. Experimental chips being built using the techniques described in this paper support 10 Gb/s links with ATM size packets.

Proposals for the provision of deterministic quality of service guarantees in integrated services networks require per-session management of traffic flowing in network switches, raising scalability questions for practical implementation of high speed packet switching in large scale networks. At the same time, the end-to-end delay bounds associated with current proposals can be overly conservative, limiting the utility of the bounds to guide efficient resource allocation. In this paper, we introduce SCED+ (surface curve earliest deadline+), a network scheduling algorithm that yields scalable provision of tight deterministic end-to-end delay bounds. These features are achieved through the use of aggregation and efficient statistical multiplexing between best-effort and guaranteed traffic. The SCEDS+ algorithm also supports statistical multiplexing between "guaranteed" traffic streams, providing tight end-to-end delay bounds for traffic streams which can tolerate non-zero packet loss rates. In order to facilitate the analysis of SCED+, we refine the so-called "network calculus" to address delay jitter, and introduce a simple and unified approach to the analysis of output burstiness of traffic departing from a general network element.

Architectures for packet switches are approaching the limit of electronic switching speed. This raises the question of how best to utilize advances in photonic technology to enable higher speeds. The authors introduce cascaded optical delay line (COD) architectures. The COD architectures utilize an extremely simple distributed electronic control algorithm to configure the states of 2/spl times/2 photonic switches and use optical fiber delay lines to temporarily buffer packets if necessary. The simplicity of the architectures may also make them suitable for "lightweight" all-electronic implementations. For optical implementations, the number of 2/spl times/2 photonic switches used is a significant factor determining cost. The authors present a "baseline" architecture for a 2/spl times/2 buffered packet switch that is work conserving and has the first-in, first-out (FIFO) property. If the arrival processes are independent and without memory, the maximum utilization factor is /spl rho/, and the maximum acceptable packet loss probability is /spl epsiv/, then the required number of 2/spl times/2 photonic switches is O(log(/spl epsiv/)/log(/spl gamma/)), where /spl gamma/=/spl rho//sup 2//(/spl rho//sup 2/+4-4/spl rho/). If one modifies the baseline architecture by changing the delay line lengths then the system is no longer work conserving and loses the FIFO property, but the required number of 2/spl times/2 photonic switches is reduced to O(log[log(/spl epsiv/)/log(/spl gamma/)]). The required number of 2/spl times/2 photonic switches is essentially insensitive to the distribution of packet arrivals, but long delay lines are required for bursty traffic.

We propose a new scheduling policy, called SCED (service curve-based earliest deadline first), which provides guarantees to virtual circuits in packet-switched networks. This scheduling policy is developed for a general framework for service provisioning based on service curves proposed by Cruz (1992). Instead of explicitly guaranteeing a specific quality of service measure, such as maximum delay, SCED guarantees the service curve for a connection. Quality of service guarantees for the connection can then be expressed as simple functions of the service curve guarantee and the traffic burstiness constraint of the connection. A simple and convenient condition under which SCED can simultaneously guarantee a set of service curves is proved. The service curve specification gives greater flexibility to a server in allocating its resources to meet diverse delay and throughput requirements. We demonstrate by an example that SCED provides a larger schedulability region than scheduling policies such as virtual-clock and PGPS with rate proportional assignment.

We review some recent results regarding the problem of providing deterministic quality of service guarantees in slot-based virtual circuit switched networks. The concept of a service curve is used to partially characterize the service that virtual circuit connections receive. We find that service curves provide a convenient framework for managing the allocation of performance guarantees. In particular, bounds on end-to-end performance measures can be simply obtained in terms of service curves and burstiness constraints on arriving traffic. Service curves can be allocated to the connections, and we consider scheduling algorithms that can support the allocated service curves. Such an approach provides the required degree of isolation between the connections in order to support performance guarantees, without precluding statistical multiplexing. Finally, we examine the problem of enforcing burstiness constraints in slot-based networks.>

We consider the problem of finding the worst case packet transit delay in networks using deflection routing. Several classes of networks are studied, including many topologies for which deflection routing has been proposed or implemented (e.g., hypercube, Manhattan Street Network, shuffle-exchange network). We derive new upper bounds on the evacuation time of batch admissions, and present simple proofs for several existing bounds. Also derived are bounds on worst case transit delay for certain networks admitting packets continuously. To demonstrate the practical utility of our results, we compare a new delay bound to the maximum delay observed in simulations. The results have application in both protocol design and the determination of the required capacity of packet resequencing buffers.>

Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p. At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is roughly, at least H(p)/(1-h(q), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable in the case where the packet always begins at a fixed node. Also considered is the maximum, over all pairs of nodes in a graph, of the mean transit time from one node to the other. The work is motivated by the search for graphs that work well in conjunction with deflection routing in communication networks.>

The circuit switching concept of trunk grouping has been introduced into the broadband packet switch. This trunk grouping concept exploits the very high bandwidth offered by lightwave technology with electronic switching technology operating at substantially slower speeds. A key component of this concept is the multichannel switch, which is a device capable of supporting routing requirements at the trunk group level. The statistical data fork (SDF), which is a multichannel switch enjoying an extremely simple control structure, is introduced here. It is based on the concepts of deflection routing and error correcting codes. It is shown that by properly designing the SDF, an extremely reliable and fault tolerant broadband switch can be obtained.>

A calculus is developed for obtaining bounds on delay and buffering requirements in a communication network operating in a packet switched mode under a fixed routing strategy. The theory developed is different from traditional approaches to analyzing delay because the model used to describe the entry of data into the network is nonprobabilistic. It is supposed that the data stream entered into the network by any given user satisfies burstiness constraints. A data stream is said to satisfy a burstiness constraint if the quantity of data from the stream contained in any interval of time is less than a value that depends on the length of the interval. Several network elements are defined that can be used as building blocks to model a wide variety of communication networks. Each type of network element is analyzed by assuming that the traffic entering it satisfies bursting constraints. Under this assumption, bounds are obtained on delay and buffering requirements for the network element; burstiness constraints satisfied by the traffic that exits the element are derived.>

For pt.I see ibid., vol.37, no.1, p.114-31 (1991). A method to analyze the flow of data in a network consisting of the interconnection of network elements is presented. Assuming the data that enters the network satisfies burstiness constraints, burstiness constraints are derived for traffic flowing between network elements. These derived constraints imply bounds on network delay and buffering requirements. By example, it is shown that the use of regulator elements within the network can reduce maximum network delay. It is also found that such a use of regulator elements can enlarge the throughput region where finite bounds for delay are found. Finally, it is shown how regulator elements connected in series can be used to enforce general burstiness constraints.>

A study is made of the average delay and the blocking probability of a regulator with a finite buffer size fed with Poisson and batch Poisson streams. The blocking probability depends only on sigma and B through sigma +B where B is the buffer size and sigma is expressed as an integer multiple of the packet size. The provision of regulator buffers allows flexibility in the traffic control such that incoming traffic can be delayed during minor overloads and rejected during major overloads. In addition, the provision of regulator buffers allows the use of smaller network buffers, which are typically more expensive due to high-speed operation. Also studied is the packet departure process from the regulator. A four-parameter descriptor ( sigma , rho , C/sub a//sup 2/, lambda ) is proposed to characterize the output process of the regulator. In addition, formulas are proposed to construct the four-parameter descriptor for the output process of the multiplexer. Such descriptors may be useful in multihop situations. Simulation results indicate that the proposed approximations are close to the simulated values.>

The author studies maximum delay in buffered multistage interconnection networks. His model differs from most in its assumptions about the traffic entering the network. Instead of using a stochastic model for the entering traffic, it is assumed that the entering traffic is unknown but satisfies certain regularity constraints. In case these constraints would not otherwise be satisfied, it is possible to devise and analyze processing (and the associated delay) that can be performed so that the constraints are satisfied. The constraints considered are well suited for bounding parameters of interest. For example, bounds on maximum network delay for each user of the network are easily obtained. The methods presented can be applied to a wide variety of models for network operation and configuration.>

A new upper bound of0.6126packets/slot is established for the through-put of a time-slotted multi-access broadcast channel subject to an infinite population of user stations (whose transmissions are modeled by a Poisson process) using (0)-, (1)-, (e)-feedback to denote a slot with none, one, or at least two packets, respectively.