Loading...
Please wait, while we are loading the content...
Similar Documents
5 Adversarial Queueing Theory I -queueing 5.1 the Adversarial Injection Model 5.2 Queueing Disciplines
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | So far, we mostly looked at static routing problems such as BMFPs, i.e. all demands (or packets) are given from the beginning and no new demands (or packets) arrive during the routing. In the real world, however, packets are usually injected at the nodes in a continuous fashion. Models that take this into account are called dynamic routing models, as opposed to the static routing models we mostly considered before. These models can be usually characterized as either stochastic or adversarial. In stochastic models, the injection of packets is modelled with the help of stochastic processes, whereas in the adversarial model it is assumed that an adversary controls the injection of new packets [2]. In this section, we restrict ourselves to considering the following variant of the adversarial model, which is due to [1]. In this model we have an adversary that is allowed to demand network bandwidth up to some specified limit. That is, it is allowed to choose any node at any time step to inject a new packet and it is allowed to select any path for the injected packet as long as the load of the edges does not exceed a certain limit. More formally, for any w, λ > 0, an adversary is called a (w, λ)-bounded adversary if for all edges e and all time intervals I of length w, it injects no more than λ · w packets during I that contain edge e in their routing paths. λ is called the injection rate and w is called the burstiness of the adversary. We demand that the adversary has to tell the system the paths it selects. Thus, we are left with solving a dynamic scheduling problem. An algorithm for this problem is called a scheduling protocol. A scheduling protocol is called stable for some λ and some network G if for any injection rate of at most λ and any paths selected for the packets in G the (expected) worst-case routing time of a packet (i.e. the time it spends in the system) does not grow unboundedly with time. Since an edge can transport at most one packet per step, λ can be at most 1. A protocol that is stable for any network and any λ < 1 is called universally stable. We will show that there are both universally stable and non-universally stable protocols. Usually, every node has a packet … |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.jhu.edu/~scheideler/courses/600.348_F02/lecture_5.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
