Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA new queueing strategy for the Adversarial Queueing Theory
140
0
0.0
(
0
)
Added by
Michael Hilker
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the todays Internet and TCP/IP-networks, the queueing of packets is commonly implemented using the protocol FIFO (First In First Out). Unfortunately, FIFO performs poorly in the Adversarial Queueing Theory. Other queueing strategies are researched in this model and better results are performed by alternative queueing strategies, e.g. LIS (Longest In System). This article introduces a new queueing protocol called interval-strategy that is concerned with the reduction from dynamic to static routing. We discuss the maximum system time for a packet and estimate with up-to-date results how this can be achieved. We figure out the maximum amount of time where a packet can spend in the network (i.e. worst case system time), and argue that the universal instability of the presented interval-strategy can be reached through these results. When a large group of queueing strategies is used for queueing, we prove that the interval-strategy will be universally unstable. Finally, we calculate the maximum time of the static routing to reach an universal stable and polynomial - in detail linear - bounded interval-strategy. Afterwards we close - in order to check this upper bound - with up-to-date results about the delivery times in static routing.
rate research
Read More
Blockchain has many benefits including decentralization, availability, persistency, consistency, anonymity, auditability and accountability, and it also covers a wide spectrum of applications ranging from cryptocurrency, financial services, reputation system, Internet of Things, sharing economy to public and social services. Not only may blockchain be regarded as a by-product of Bitcoin cryptocurrency systems, but also it is a type of distributed ledger technology through using a trustworthy, decentralized log of totally ordered transactions. By summarizing the literature of blockchain, it is found that more papers focus on engineering implementation and realization, while little work has been done on basic theory, for example, mathematical models (Markov processes, queueing theory and game models), performance analysis and optimization of blockchain systems. In this paper, we develop queueing theory of blockchain systems and provide system performance evaluation. To do this, we design a Markovian batch-service queueing system with two different service stages, while the two stages are suitable to well express the mining process in the miners pool and the building of a new blockchain. By using the matrix-geometric solution, we obtain a system stable condition and express three key performance measures: (a) The number of transactions in the queue, (b) the number of transactions in a block, and (c) the transaction-confirmation time. Finally, We use numerical examples to verify computability of our theoretical results. Although our queueing model is simple under exponential or Poisson assumptions, our analytic method will open a series of potentially promising research in queueing theory of blockchain systems.
This paper investigates a partially observable queueing system with $N$ nodes in which each node has a dedicated arrival stream. There is an extra arrival stream to balance the load of the system by routing its customers to the shortest queue. In addition, a reward-cost structure is considered to analyze customers strategic behaviours. The equilibrium and socially optimal strategies are derived for the partially observable mean field limit model. Then, we show that the strategies obtained from the mean field model are good approximations to the model with finite $N$ nodes. Finally, numerical experiments are provided to compare the equilibrium and socially optimal behaviours, including joining probabilities and social benefits for different system parameters.
Scheduling and managing queues with bounded buffers are among the most fundamental problems in computer networking. Traditionally, it is often assumed that all the properties of each packet are known immediately upon arrival. However, as traffic becomes increasingly heterogeneous and complex, such assumptions are in many cases invalid. In particular, in various scenarios information about packet characteristics becomes available only after the packet has undergone some initial processing. In this work, we study the problem of managing queues with limited knowledge. We start by showing lower bounds on the competitive ratio of any algorithm in such settings. Next, we use the insight obtained from these bounds to identify several algorithmic concepts appropriate for the problem, and use these guidelines to design a concrete algorithmic framework. We analyze the performance of our proposed algorithm, and further show how it can be implemented in various settings, which differ by the type and nature of the unknown information. We further validate our results and algorithmic approach by a simulation study that provides further insights as to our algorithmic design principles in face of limited knowledge.
Monitoring network state can be crucial in Future Internet infrastructures. Passive monitoring of all the routers is expensive and prohibitive. Storing, accessing and sharing the data is a technological challenge among networks with conflicting economic interests. Active monitoring methods can be attractive alternatives as they are free from most of these issues. Here we demonstrate that it is possible to improve the active network tomography methodology to such extent that the quality of the extracted link or router level delay is comparable to the passively measurable information. We show that the temporal precision of the measurements and the performance of the data analysis should be simultaneously improved to achieve this goal. In this paper we not only introduce a new efficient message-passing based algorithm but we also show that it is applicable for data collected by the ETOMIC high precision active measurement infrastructure. The measurements are conducted in the GEANT2 high speed academic network connecting the sites, which is an ideal test ground for such Future Internet applications.
The number of electric vehicles (EVs) is expected to increase. As a consequence, more EVs will need charging, potentially causing not only congestion at charging stations, but also in the distribution grid. Our goal is to illustrate how this gives rise to resource allocation and performance problems that are of interest to the Sigmetrics community.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
