|
|
|
|
In this paper we present a parameter estimation method for the bandwidth forward pricing model of Keppo (2001). Bandwidth forwards are modeled by using underlying fixed routing capacity prices and routing options. The estimation of the model parameters is based on the existing price data and we compute the implied parameters of the model. According to the presented estimation method we can calculate an exact forward curve of a connection if we know the forward curves of the surrounding connections, because those forward curves contain sufficient information about the estimated forward curve.
In controlling a stochastic network, an escape time criterion is useful if one wishes to regulate the occurrence of buffer overflow. We formulate a risk-sensitive escape time criterion which penalizes exits that occur on short time intervals more heavily than ordinary escape time criteria. The optimal value is studied in the large buffer limit, and related to a deterministic differential game with constrained dynamics. We prove that the game has value which is a (viscosity) solution of a PDE. For a simple network, the value and optimal control are computed, demonstrating the applicability of the approach.
This paper describes a two-phase heuristic method for scheduling and dispatching production in a wafer fab. In the first phase, the fab production flow is modeled as a multiclass fluid network which is an approximation of a discrete flexible job-shop with WIP and ongoing inputs. However, buffer levels are allowed to have continuous non-integer values, equipment processing can be simultaneously shared between different products, and a single lot can begin processing at a downstream step before it finishes at the previous step. By solving a finite series of linear or quadratic programs, an optimal policy for this fluid relaxation problem is found. In the second phase, production in the wafer fab is scheduled ahead of time or dispatched in real time by minimizing the deviation of the production from the optimal fluid control policy.
We represent a data network as a set of links shared by a dynamic number of competing flows. These flows are generated within sessions and correspond to the transfer of a random volume of data on a pre-defined network route. The evolution of the stochastic process describing the number of flows on all routes, and the performance of the data transfers, depend on how link bandwidth is allocated between concurrent flows. We use some key properties of Whittle networks to characterize the class of bandwidth allocations which are insensitive in the sense that the stationary distribution of this stochastic process does not depend on any traffic characteristics (session structure, data volume distribution) except the traffic intensity on each route. We show in particular that this insensitivity property does not hold in general for well-known allocations such as max-min fairness or proportional fairness.
We discuss the steady-state distributions, diffusion approximations and performance comparisons for priority multiclass queueing networks associated with high-speed integrated services packet networks (ISPN) like Internet (IP), asynchronous transfer mode (ATM) and frame relay (FR) networks. The product-form solutions are derived for these queueing networks with multi-server stations under exponential interarrival and service time distributions, which can be used as performance comparison criteria for diffusion approximations and simulation studies of large scale networks with multi-processor and/or multistage shared-memory switches. Recently, W.Dai (2001) proved the diffusion approximations for the queueing networks with single-server stations under general interarrival and service time distributions, and showed that there is certain proportional relationship among different classes of queue lengths in a switch in the approximating semimartingale reflecting Brownian motion (SRBM). This property referred to as state space collapse will largely reduce the dimension of analysis, computation and simulation for buffer management among different classes of packets. Hence SRBM can be developed as performance evaluation models for high-speed ISPN with multistage shared-memory switches. For example, they can be used to estimate suitable buffer sizes for switches and expected end-to-end delays for various types of packets in core networks, which may reduce packet loss ratio for non-real time traffic and delay for real time traffic. Comparison examples will be given to show the usage of our exact solutions and the effectiveness of diffusion models.
We develop a dynamic network provisioning methodology for real time bandwidth services that minimally satisfies customer QoS (blocking probability) requirements. Our method is sufficiently general and accommodates time varying trends in the demand for services as well as different bandwidth requests for multiple classes of customers. Asymptotic results and bounds for the Erlang loss system due to Jagerman are invoked to obtain simple approximate solutions to this bandwidth provisioning problem.
We consider an ad-hoc wireless network where the wireless links from each node to its neighbors are modeled by a probability distribution describing the local broadcast nature of wireless transmissions. We provide several optimal routing strategies in such a network. In reality the probability distributions describing the broadcast models are estimated in real-time. This implies that the optimality of the proposed routing strategies depends on the estimation precision. Therefore, we also investigate the impact of estimation errors on the performance of the proposed routing policies.
In-order delivery of packets is a de facto feature of all packet switches in use today. Research in parallel packet switches (Chang 2001, Iyer 2001) demonstrated that very fast and very scalable switching is possible, yet guarantee of in-order delivery is lost. The tradeoff between load-balancing and in-order delivery is in fact apparent, as load-balancing is most efficient when packets may be scheduled to parallel datapaths without considering additional constraints regarding what comes before and after.
While many researchers strive to recover in-order delivery, we seek to capitalize on the computational savings, which are as much as O(N^2.5), when in-order delivery may be foregone justifiably. We motivate our work by pointing to two such possibilities: (1) there is a large class of end-systems whose traffic comprises single packets, such as Auto-ID and product tags, telemetry, control and signaling packets; (2) increasing computation power is making application level framing (Clark 1990) a viable option for many end-systems.
In this work, we consider a partitioning approach to switching packets with and without in-order guarantee in an integrated architecture. We obtain a simple two-partition switch by modifying Chang's two-stage switch to recover in-order delivery for some of the packets, while end-systems are incentivized to label packets according to whether in-order delivery is desirable. The proportion of in-order delivery may also be adjusted, presumably to match its expected relative demand. Finally, we speculate on the future of Internet switching if out-of-order delivery indeed becomes widely acceptable.
We discuss fractional Brownian motion (fBm) analogues of the thinning, merging and "uniformity of arrivals" properties of Poisson processes. fBm is one of the simplest models of long range dependent (LRD) traffic in a networking context, hence any properties that fail to hold for fBm are unlikely to hold for more general LRD traffic. Conversely, proofs of any properties that do hold for fBm may provide clues to analogous properties in the more general LRD case.
This paper studies the stability of network models that capture macroscopic features of data communication networks including the Internet. The network model consists of a set of links and a set of possible routes which are fixed subsets of links. A connection is dynamically established along one of the routes to transmit data as requested, and disconnected after the transmission is over. The transmission bandwidth of a link is dynamically allocated, according to a specific bandwidth allocation policy, to ongoing connections that traverse the link. A network model is said to be stable under a given bandwidth allocation policy if, roughly, the number of ongoing connections in the network remains bounded over all time. We consider a stationary and a bursty network model. The former assumes stochastically stationary arrival processes of connections as in many theoretical studies, while the latter allows more realistic bursty and correlated arrival processes. For both models under a necessary stability condition (i.e., the average offered transmission load on each link is within its bandwidth capacity), we show that the proportionally fair, the minimum potential delay, the max-min fair and a class of utility maximizing bandwidth allocation policies ensure network model stability, while some priority oriented policies and the maximum throughput policy do not. Interestingly, the bandwidth allocation policy that maximizes the arctan($\cdot$) utility ensures the stability of the stationary model but not the bursty model. This raises a serious concern on the current practice in Internet protocol design, since such a policy is thought as a good approximation of the most widely used TCP in the current Internet.