
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00006586/00001
Material Information
 Title:
 A comparative study of broadcasting on multiple access channels
 Creator:
 Alkhafaji, Mustafa A. ( author )
 Place of Publication:
 Denver, Colo.
 Publisher:
 University of Colorado Denver
 Publication Date:
 2017
 Language:
 English
 Physical Description:
 1 electronic file (46 pages) : ;
Thesis/Dissertation Information
 Degree:
 Master's ( Master of science)
 Degree Grantor:
 University of Colorado Denver
 Degree Divisions:
 Department of Computer Science and Engineering, CU Denver
 Degree Disciplines:
 Computer science
Subjects
 Subjects / Keywords:
 Packet switching (Data transmission) ( lcsh )
Queuing theory ( lcsh ) Routing (Computer network management) ( lcsh )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Review:
 We study broadcasting on multiple access channels by deterministic distributed algorithms. Packet injections are determined by adversarial models. The power of a worstcase adversary is constrained by the rate of injection and a bound on the number of di.
 Bibliography:
 Includes bibliographical references.
 System Details:
 System requirements: Adobe Reader.
 Statement of Responsibility:
 by Mustafa A. Alkhafaji.
Record Information
 Source Institution:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 on10238 ( NOTIS )
1023865262 ( OCLC ) on1023865262
 Classification:
 LD1193.E52 2017m A55 ( lcc )

Downloads 
This item has the following downloads:

Full Text 
A COMPARATIVE STUDY OF BROADCASTING ON MULTIPLE ACCESS
CHANNELS
by
MUSTAFA A. ALKHAFAJI B.S., ThiQar University, 2011
A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Computer Science Program
2017
This thesis for the Master of Science degree by Mustafa A. Alkhafaji has been approved for the Computer Science Program by
Bogdan S. Chlebus, Chair Farnoush BanaeiKashani Ellen Gethner
Date:December 16, 2017
n
Alkhafaji, Mustafa A. (M.S., Computer Science Program)
A Comparative Study of Broadcasting on Multiple Access Channels Thesis directed by Bogdan S. Chlebus
ABSTRACT
We study broadcasting on multiple access channels by deterministic distributed algorithms. Packet injections are determined by adversarial models. The power of a worstcase adversary is constrained by the rate of injection and a bound on the number of different packets that could be injected in one round. We propose models of packet injections that conform to worstcase adversarial constraints but have stochastic components that can be simulated. We implement and simulate a number of deterministic and randomized broadcast algorithms. The performance of broadcast algorithms is measured by packet latency. We compare various broadcast algorithms by their performance in simulations.
The form and content of this abstract are approved. I recommend its publication.
Approved: Bogdan S. Chlebus
m
DEDICATION
I dedicate this work to my parents, and to my whole family who have supported me throughout the time of this work and motivated me to challenge the difficulties of life and become the person who I am.
IV
ACKNOWLEDGMENTS
I want to thank the Higher Committee of Education Development in Iraq (HCED) for supporting my studies at the University of Colorado Denver.
Special thanks go to my advisor Bogdan Chlebus for his guidance through this work.
I owe many thanks to my dear friend Mohammed Qasim for his encouragement and advice.
v
TABLE OF CONTENTS
I. INTRODUCTION ................................................ 1
II. RELATED WORK................................................. 3
III. TECHNICAL PRELIMINARIES..................................... 6
IIII. BROADCAST ALGORITHMS ..................................... 13
4.1 Distributed Deterministic Algorithms................... 14
4.2 Adhoc Deterministic Algorithms........................ 16
4.3 Randomized Algorithms.................................. 17
V. THE METHODOLOGY OF EXPERIMENTS.............................. 18
5.1 Specific Experiments .................................. 19
5.1.1 Deterministic Distributed Algorithms............ 20
5.1.2 Randomized Versus Deterministic Distributed Algorithms . 27
5.1.3 Varying Burstiness ............................... 30
5.1.4 Varying Numbers of Stations....................... 31
5.2 Throughput ............................................ 33
5.3 Future Work............................................ 34
VI. CONCLUSION.................................................. 35
REFERENCES.................................................... 37
vi
LIST OF TABLES
Table
5.1 Observed values of average, maximum packet latency and worstcase for
varying injection rates. Parameter values: R = 100, 000; n = 200; b = 20. 21
5.2 Throughput............................................................ 33
LIST OF FIGURES
Figure
5.1 Algorithm RRW. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? =
100, 000; n = 200; b= 20.................................................. 20
5.2 Algorithm MBTF. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? =
100, 000; 77. = 20; 6 = 8................................................. 22
5.3 Algorithm SRR. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? = 100, 000; n =
200....................................................................... 23
5.4 Algorithm OFRRW. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? =
100, 000; 77. = 50; 6 = 8................................................. 24
5.5 Algorithm OFSRR. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? =
100, 000; 77. = 50; 6 = 8................................................. 25
5.6 Seven deterministic algorithms. Observed values of maximum packet latency for varying injection rates. Parameter values:/? = 100, 000; n =
20; b =20.................................................................... 26
5.7 Randomized algorithms. Observed values maximum packet latency for
varying injection rates. Parameter values:/? = 100, 000; n = 20; b = 20. . 27
5.8 Three deterministic algorithms. Observed values of maximum packet latency for varying injection rates. Parameter values:/? = 100, 000; n =
20; b =20.................................................................... 28
5.9 Four Backoff algorithms. Observed values of maximum packet latency for
varying injection rates. Parameter values:/? = 100, 000; n = 80; b = 20. . 29
5.10 Three deterministic algorithms. Observed values maximum packet latency for varying Burstiness. Parameter values:/? = 100, 000; n = 10; injection
rate is 1.................................................................... 30
5.11 Observed values maximum packet latency for varying number of stations.
Parameter values:/? = 100, 000; b = 20; injection rate = 0.75............. 31
5.12 Observed values maximum packet latency for varying number of stations.
Parameter values:/? = 100, 000; b = 20; injection rate = 0.75............. 32
viii
CHAPTER I
INTRODUCTION
A multiple access channel is a formal model of of a broadcasting environment. It is an abstraction of the Ethernet [16], which is the most popular implementation of local area networks.
There are a number of nodes (stations) attached to a channel. Multiple soverlapping transmissions result in an interference, which is also called a collision for access to the transmitting medium. The semantics of multiple access channels is defined by two properties:
(1) when one station transmits then the message is heard by all the stations.
(2) multiple overlapping transmissions collide with each other and none is heard on the channel.
We consider the slotted model of a channel in which an execution of a broadcast algorithm is partitioned into rounds, so that it take a round to transmit one message and multiple messages transmitted in the same round result in a collision.
We discuss and compare distributed broadcast algorithms when packets are injected continuously into stations. The numbers of packets injected into the stations are constrained by a leakybucket adversarial model [1, 5, 9, 11, 12].
The adversarial model which provides an upper bound on the amount of generated traffic is determined by two parameters: injection rate and burstiness, and is understood as is known as a leakybucket adversarial model. Packet injection denotes an upper bound on the average number of packets injected per round, averaged over all possible time intervals. Burstiness is defined as the maximum number of packets that can be injected in a round.
The simulations we design constrain the number of packets generated such that they always conform to an adversary with some injection rate p and burstiness b. Packets are initially generated with a suitable Poisson distribution, which has its
1
parameter A adjusted to p. This together gives three parameters: (p,X,b).
The number of stations that attached to the channel is fixed and their number n is known, in that it can be used in codes of algorithms. Stations are supplied with private queues, in which they can store packets until they are heard on the channel.
The performance of broadcast algorithms is measured by packet latency. It could be understood either in the worstcase, for a suitable adversarial model, or in the average sense, subject to stipulations of packet injection that involves randomization in packet generation.
The traditional algorithmic approach to broadcast on multiple access channels in a distributed manner uses randomization to arbitrate for access to the channel. Such randomized algorithms include backoff protocols, such as the binary exponential backoff used in the Ethernet [16] suite of technologies.
Recently, deterministic broadcast algorithms were proposed and showed to have bounded packet latency in the worst case in adversarial models determined by injection rate and burstiness. We simulate both deterministic algorithms and randomized ones.
The thesis compares various algorithms through simulations. The theoretical worstcase upper bounds on packet latency are compared to bounds obtained in simulations, both average and maximum.
2
CHAPTER II
RELATED WORK
There is an rich literature on algorithms for multiple access channels, see the surveys [10, 13]. The methodology of adversarial queuing was considered extensively in the literature [7, 8, 9, 11, 12].
Some studies that related with this types of project is considered packet routing when packets are injected continuously into a network. They evolved an adversarial theory of queuing reached at addressing some of the limitations queuing theory based on fixedtime constant generation and origin in probabilistic analysis. They test the stability and reliability of queuing networks and behavior when the arrival data are adversarial [9] .
Anantharamu and Chlebus [1] study broadcast in multiple access channels in dynamically adversary form. There is an unlimited bound provide of stations that dont have names attached to a synchronous channel. There is an adversary that injects packets into stations to be broadcast on the channel. The adversary is constrained by burstiness, injection rate, and by number of passive stations that can be concurrently activated by providing them packets. They consider deterministic distributed broadcast algorithms, who are further classified by their attributes. They show for which injection rates can algorithms investigate bounded packet latency, when adversaries are determined to be able to activate at most one station per round. The rates of algorithms they introduce make the increasing sequence consisting of 1/3, 3/8 and 1/2 give a picture of the additional properties of algorithms. Also, they show that injection rate 3/4 couldnt be handled with bounded packet latency.
Most previous work on broadcasting on multiple access channel has been carried out assuming that randomization has related part to play with. When packets are created subject to stochastic limitations, randomness can affect on the status of protocols either actively, by being a part of the mechanism of a randomized protocol,
3
or passively. The randomize environment as a part of its specification determined in such a way can be represented as a Markov chain so that stability could be understood as ergodicity. For the recent work on the algorithmic of randomized broadcasting on multiple access channels, see [14, 18].
Andrews and Zhang [6] developed scheduling and routing in wireless networks where each node can be transmited data to at most one neighboring node per time slot. Furthermore, transmission rates and data arrivals are governed by an adversary. They generated scheduling algorithms that ensure network stability for the case in which the adversary specifies the links that the data must transmission through. Bender [7] applied adversarial approach to study the issue of productivity of randomized backoff for multipleaccess channels in the queue free model.
Injection rate is defined as the large average number of messages generated in a category of slots of rounds. Burstiness is the maximum number of packets an adversary could inject in a round. There are two regular models of adversaries in adversarial queuing. When there is no limitation imposed on intervals time to average packets, then this category of adversaries is called leaky bucket. If we average only over intervals of a constant length, then it is called window size; such adversaries are of window type. In the concept of adversarial queuing, window adversaries were first used by [9] and leakybucket adversaries by [6]
Anantharamu et al. [3] proposed how to compare dynamic broadcasting versus adversaries that are unbounded in the sense that they can inject packets into randomly stations with no restrictions on their numbers nor rates of injection. They gave a deterministic algorithm optimal with respect to struggle performance, when measuring either the maximum queue size or the total number of packets in the system. In addition, they showed that the algorithm is stochastically optimal for any expected injection rate smaller than or equal to 1.
Anantharamu et al. [4] studied broadcasting on multiple access channels with
4
jamming and dynamic packet arrivals. The communication platform is represented by adversarial models which specify restricts on packet arrivals and jamming. They consider deterministic distributed broadcast algorithms and give upper bounds on the (worstcase) packet latency and the number of queued packets that relating to the defining adversaries. Packet arrivals are specified by number of packets that can arrive in one round and the rate of injections. Jamming is limited by the number of consecutive rounds that can be jammed and by the rate with which the adversary can jam rounds.
5
CHAPTER III
TECHNICAL PRELIMINARIES
A multiple access channel is a broadcast network that allows for each node to transmit its message to all the other nodes in one round. We consider such synchronous networks when executions of communication algorithms are structured as a series of rounds.
It is assumed that a multiple access channel consists the communication medium and some nodes connected to it. Nodes that have packets to transmit are called active and otherwise they are passive.
The set of nodes may be considered to be either static or dynamic, depending on our preference of the model. In the static model, there is a fixed set of some n nodes. In this case, the nodes usually have fixed names that identify them, which are unique integers in the range [0, n 1]. In the dynamic case, nodes may join and leave the system, they do not have fixed names, and only active nodes execute a broadcast algorithm while passive nodes are neutral. There is an unbounded supply of passive nodes in the dynamic model, and a packet may be injected into a passive node, which immediately becomes active.
It is said that a node hears a transmission when it receives it successfully. The critical property of multiple access channels is how multiplicity of concurrent transmissions affects hearing messages.In general, there are three possible cases of relevant multiplicities of transmissions in a round: no nodes transmit, exactly one node transmits, and multiple (more than one) nodes transmit.When multiple nodes transmit in a round then this is referred to as a collision occurring in this round.
When no node transmits in a round then the channel is silent, which is reflected by the corresponding silence feedback received from the channel by each node. When only one node transmits then all the other nodes that are actively participating in the execution hear the transmitted message, which is the feedback they receive from
6
the channel. When multiple nodes transmit in the same round then this creates a collision, to the effect that the messages interfere with each other and none can be heard by any attached node. In this case, the attached nodes hear a collision signal as the feedback from the channel.
Multiple access channels come in two variants, which are determined by the feedback obtained from the channel when a message is not heard. The channel without collision detection has the property that the silence and collision signals are identical, while in the channel with collision detection they are different, so the nodes can distinguish between the two corresponding cases. The feedback obtained from the channel in a round does not depend what a node does in this round; in particular, a transmitting node and a pausing node receive the same feedback, and if a message is heard then the transmitting node hears the message as well.
We consider dynamic broadcasting when packets are injected by adversaries. Various types of adversaries considered in this paper, they are all specializations of the leaky bucket adversarial concept. A leakybucket adversary is determined by the following two key numeric parameters. One is injection rate, denoted p, which is a real number satisfying 0 < p < 1. The other is burst component, denoted b, which is a positive integer. Together they make the type (p, b) of the adversary.
In each round, the leakybucket adversary of type (p, b) injects a number of packets, which can be visualized as occurring in two stages: first the number of new packets to be injected is determined for the round, and then these many packets are injected into some nodes. The type of a leakybucket constrains the numbers of packets injected in each round as follows: for each contiguous time interval r of r rounds, the number of packets injected into the system during the rounds in r is at most p t + b.
This captures two postulates for the adversary of type (p, 6), that it constraints both the average number of injected packets in large intervals and also the bursts of
7
packets injected in small intervals. Indeed, the injection rate p can be interpreted as the average number of packets injected in a round when averaging over large intervals. Also, at most [p + b\ new packets can be generated in one round, because the number of new packets is a nonnegative integer and p \r\+b = p + b with r = 1.
One may consider variants of adversarial models defined by where the new packets are injected, after their number has been decided on in a round. This naturally depends on whether the adversary is static, which applies for the static model of a fixed set of nodes, or it is dynamic and so my create new active nodes and add them to the system. Historically, the most studied case was of static adversaries with no restrictions on which nodes obtain the newly generated packets. A lack of restrictions means that the adversary is to model an environment to study worst case performance of algorithms. This adversarial model was considered in [2, 3, 4, 11, 12],
The adversarial model may additionally restrict the number of passive nodes that are activated in a round. At most [p + b\ passive nodes can be activated in a round because each activation requires at least one packet.
An upper bound k on the number of stations that can be activated in a round can be considered an independent parameter of the adversary, which is then called kactivating. In particular, Anantharamu and Chlebus [1] considered 1activating dynamic adversaries. When we refer to an adversary as static or dynamic only, without specifying a bound on number of activated nodes, then this means that no restriction on the number of activations per round applies, except for the bound [p + b\.
In this thesis, it is emphasized on 1activating static adversaries. The motivation for activating at most one node in a round comes from the realworld applications when multiple access channels model local area networks and is as follows. It expects that nodes that are active usually have multiple packets to broadcast, so new packets are typically injected into nodes that are already active. It also expects that nodes
8
that are passive stay such through the round, although rarely a passive node gets activated and generates packets to broadcast. This latter interpretation means also that having multiple passive nodes activated in a round is such a rare event then it can be disregarded without distorting the performance of broadcasting as modeled in simulations. The additional advantage of 1activating adversaries is that it is possible to broadcast in a distributed deterministic manner with bounded packet latency for positive injection rates, against such adversaries, even in dynamic systems, as was shown by Anantharamu and Chlebus [1].
An alternative to adversaries conducive to studying worst case performance, It can build randomness into an adversarial model, which allows to capture the average performance. It refers to such adversaries as randomized ones and if randomness is not uses in any manner then the adversary is worstcase. A randomized leaky bucket adversary is again determined by its type (p, b). Randomness can affect the behavior of randomized leakybucket adversaries in two ways: in the process of determining the number of packets injected in a round, and in selecting nodes where the packets are injected. Each randomized adversary can also have an upper bound on the number of stations activated in a round as an additional parameter.
Now It defines randomized leakybucket adversaries of type (p, A, 6), where 0 < p < 1 and 0 < A. First we specify how to determine the number of packets injected in a round. Let D be a variable which we call the bucket. Its purpose is to remember the recent injections of packets and it is interpreted as follows: [D\ is the maximum number of packets that can be injected in the current round.
Initially, D is set to b. The number of packets injected in a given round by the randomized leakybucket adversary is determined as follows.
First bucket is upgraded D by assigning D min[T> + p, b\. This means that the inequality D < b is always satisfied.
Next, it is generated a nonnegative integer X with the Poisson distribution
9
with parameter A, which means that
Pr(X = i) = e~x j ,
l\
for each integer i > 0, see [17, 19]
Then the number j of packets injected in this round is determined as j = min{ LDJ, X}.
Finally, D is updated to D j, which means that the inequality D > 0 is always satisfied.
This completes the manipulations of D in this round.
Proposition 1 When a randomized adversary of type (p,X,b), injects packets in a sequence of consecutive rounds then the numbers of packets generated in each round satisfy the requirements of the worstcase adversary of type (p,b), for 0 < p < 1 and 0 < A.
Proof: It needs to show that the randomized adversary injects at most p r + b packets in each interval r. Injecting a packet results in decrementing D to D 1. So the number of packets that can be injected is accounted for by all the increments of D and the initial value of D. The bucket D is incremented by at most p in the beginning of each round in r, for the total of at most p r during all the rounds in r. Additionally, the bucket satisfies D < b before the first round of r begins.
The Poisson distribution with parameter A has the property that E[X] = A, but the expected number of packets injected in a round is smaller than A because D is the additional upper bound.
Let Y be the random variable equal to the number of packets injected in a round by a randomized adversary of type (p, A, 6). It would be interesting to find E[T] beyond the estimate E[T] < A.
10
For injection rate p < 1, one could simply use A = p in experiments. An alternative would be to use such A > p that EY] = p. Then the correspondence between the worst case adversary of type (p, b) and the randomized adversary of type (p, A, b) would be even closer than what Proposition 1 gives.
After having determined the number of packets j to inject, It needs to determine where the j new packets are injected. Let the adversary be fcactivating, where k < [b + pj. There are the dynamic and statice cases.
First the dynamic case. In a given round, consider k new virtually active nodes. The set of active and virtually active nodes makes the set of nodes eligible for this round. Each among the new j packets is assigned an eligible station uniformly at random, with assignments of different packets made independently. If a virtually active station receives a packet then it becomes added to the system as active otherwise it disappears.
Next, the static case. Let Â£ be the number of passive nodes among all the n nodes. The adversary selects min{Â£, k} such stations uniformly at random as virtually active. In particular, if Â£ = k then all passive nodes become virtually active and if Â£ = 0 then there is no virtually active node. Again, the set of active and virtually active nodes makes the set of nodes eligible for this round, and also each of new i packets is assigned an eligible station uniformly at random, with assignments of different packets made independently.
Each execution of a randomized leaky bucket adversary of a given type satisfies the specialization of the worstcase leaky bucket adversary of this type, in the sense that each pattern of injections of packets satisfies the constrains defining the worstcase adversary. It follows that bounds on performance metrics of deterministic algorithms against the deterministic leaky bucket adversary apply to the randomized version of the adversary of the same type.
The randomized leaky bucket adversary of a given type can be simulated by
11
generating uniform distributions on finite ranges and a Poisson distribution for a given injection rate interpreted as the expectation of this Poisson distribution.
12
CHAPTER IIII
BROADCAST ALGORITHMS
It is mostly concerned with deterministic distributed algorithms. Such an algorithm is to perform dynamic broadcasting, in the sense that packets get injected into the nodes and the nodes have these packets heard on the channel by successful transmissions.
An algorithms is activation based when a station without a packet to transmit ignores the feedback from the channel and starts participating actively only starting from a round when it gets activated by having a packet injected into it and stays such as ling as it has packets to transmit. An algorithm is full sensing when all the nodes listen to the channel at all times.
The actions in a round of a node executing a full sensing algorithm or activation based when a station has a packet to transmit are as follows. The node first either transmits a packet or pauses, as determined by its state. Then the nodes obtains the feedback from the channel, the same as all the other stations. Next, the node may have a number of packets injected into it in the round. Finally, the node performs local computation, which can be interpreted as a state transition. This involves the following actions. If packets were injected then they are enqueued in the local queue. Local variables are updated, depending on what occurred in the round up to this moment. The node decides if to transmit in the next round and if so the it builds a message to be transmitted. If the queue includes packets then the message may include a packet.
A message transmitted on the channel may include at most one packet but it may consist of only control bits. An algorithm may not use control bits at all, then the messages transmitted int he course of its execution consist of only packets. An algorithm that has stations transmit messages with control bits is called adaptive. The messages in an execution of such an algorithm may consists of only control bits
13
but for a nonadaptive algorithm if a node does not want to transmit a packet then the node does not transmit at all.
There are three groups of algorithms: deterministic token ones, deterministic ad hoc ones, and randomized.
Algorithms designed specifically for a multiple access channel with a fixed set of nodes attached to the channel each with a unique name may operate by having the nodes exchange a token. The token visiting a node allows the node to transmit, which prevents collisions. Such algorithms could be called token ones; see[12, 11, 4], The other paradigm is for environments without a fixed set of named nodes attached to the channel, and instead nodes are dynamically generated and assigned temporary implicit names. This works for a setting in which at most one new node is added to the system in a round. Such algorithms could be called adhoc ones; see [1]. Multiple access channels with a fixed set of named nodes attached to them are more effective than channels executing ad hoc algorithms, in that the former can handle injection rate 1 in a stable manner [11] and arbitrary injection rates smaller than 1 with bounded packet latency [3, 4, 2] while ad hoc algorithms cannot handle injection rates that are at least 3/4 with bounded packet latency [1].
What follows are brief specifications of the algorithms that will be compared in experiments. There are two groups of algorithms: deterministic token ones and randomized.
4.1 Distributed Deterministic Algorithms
Let us begin with the considered token algorithms. Algorithm MoveBigToFront (MBTF) Algorithm MoveBigToFront (MBTF) is an adaptive algorithm for channels without collision detection. Each station maintains a list of all stations in its private memory. A list is initialized to be sorted in the increasing order of names of stations. The lists are manipulated in the same way by all the stations so their order is the same. The algorithm schedules exactly one station to transmit in a round,
14
so collisions never occur. This is implemented by having a conceptual token assigned to stations, which is initially assigned to the first station on the list. A station with the token broadcasts a packet, if it has any, otherwise the round is silent. A station considers itself big in a round when it has at least n packets; such a station attaches a control bit to all packets it transmits to indicate this status. A big station is moved to the front of the list and it keeps the token for the next round. When a station that is not big transmits, or when it pauses due to a lack of packets while holding the token, the token is passed to the next station in the list ordered in a cyclic fashion. Algorithm MBTF was introduced in [11] and showed to be stable for injection rate 1. It is stable for injection rate 1 and has bounded packet latency for injection rates smaller than 1 .
Algorithm RoundRobinWithholding (RRW) is a fullsensing (nonadaptive) algorithm for channels without collision detection. It operates in a roundrobin fashion, in that the stations gain access to the channel in the cyclic order of their names. Once a station gets access to the channel by transmitting successfully, it withholds the channel to unload all the packets in its queue. A silent round is a signal to the next station, in the cyclic order of names, to take over. Algorithm RRW was introduced in [12] and showed to be universal, that is, stable for injection rates smaller than 1. R has bounded packet latency for injection rates smaller than 1.
Algorithm SearchRoundRobin (SRR) is a fullsensing (nonadaptive) algorithm for chan nels with collision detection. Its execution proceeds as a systematic sweep across all the stations with the goal to identify these with packets, with such search performed in the cyclic order. When a station with a packet is identified, the station unloads all its packets one by one. A silent round triggers the sweep to be resumed. We apply binary search to identify the next station. The binary search is implemented using collision detection. When we inquire about a segment of stations, then all the stations with packets that are in the segment transmit in the round. A search
15
is completed by a packet heard. A silence indicates that the segment is empty of stations with packets. A collision indicates that multiple stations are in the segment: this results in having the segment partitioned into two halves, with one segment processed next immediately while the other one is pushed on a stack to wait. A transition to the next segment occurs when the stack gets empty. Algorithm SRR is introduced by [12]. It has bounded packet latency for injection rates smaller than 1.
The algorithms RRW and SRR can be modified by using the approach that could be called oldergofirst, which was introduced by Anantharamu et al.[2], Each of the algorithms has executions that can be interpreted as having a token that traverses all the nodes in a round robin manner. Call each such a cycle a phase. The packets that are injected in a phase are considered new during the phase and become old when the next phase starts. In the course of a phase, the new packets are ignored and only the old ones are broadcast. The resulting algorithms are called OlderFirstRoundRobinWithholding (OFRRW) and OlderFirstSearchRoundRobin (OFSRR), respectively.
4.2 Adhoc Deterministic Algorithms
Next we present the adhoc algorithms; they all were proposed by Anantharamu and Chlebus [1]. Algorithm CountingBackoff is a nonadaptive activation based algorithm for channels with collision detection.
Active nodes are stored on a virtual stack and an active station remembers its distance from the top of the stack. It was sown that the algorithm has bounded packet latency when injection rate is smaller than 1/3. Finally, there is the algorithm QueueBackoff which is an adaptive activationbased algorithm for the channel without collision detection that has bounded packet latency for injection rate 1/2.
These two algorithms do not use the names of nodes, even if they available. The bounded packet latency holds even when there is no fixed set of nodes attached to the channel and the adversary has the power to create new stations by injecting packets
16
into them, but at most one new station in a round.
4.3 Randomized Algorithms
Finally, it will simulate the behavior of two randomized algorithms. These are the BinaryExponentialBackoff (BEB) and QuadraticBackoff (QB). The backoff protocols are considered in their windowed versions. A node tries to broadcast the packets in the order of their injection. When a new packet is available then the node selects a round uniformly at random in the current window then waits for this round to occur and transmits the packet. The first window is of size 1, which means that a new packet is transmitted immediately. When a transmission is heard then the next packet is processed, otherwise when there is a collision then the window is increased and a round in it is selected from it uniformly at random. For BinaryExponentialBackoff, the zth window size was determined as 2* and forQuADRATlCBACKOFF, the zth window size was defined to be i2.where the round of a transmission is drawn from a time interval uniformly at random.
There is an option to consider these algorithms with an upper bound on the window size, as binary exponential backoff is used in the implementation of the Ethernet. For instance, the zth window size for BinaryExponentialBackoff could be 2min(10>Q which is exactly as in the Ethernet, and for QuadraticBackoff, the zth window size could be (min(z, 32))2. Observe that with these choices of constants the maximum size of a window is the same in BEB and QB. The two randomized protocols are proposed in [14, 15, 16].
17
CHAPTER V
THE METHODOLOGY OF EXPERIMENTS
We consider systems with a fixed number of stations attached to the channel, only the static case The number of nodes n is a parameter of a simulation. This is typically a small positive integer, say, in the range [1, 100]. We will consider only 1activating adversaries. The simulations will simply mimic randomized leakybucket adversaries: but only static 1activating adversaries.
It needs to specify how to terminate an experiment. For example, we may designate a certain constant L as a parameter. This constant L denotes the number of rounds during which new packets are injected for which is measured packet latency. The precise meaning of L is as follows: packets are injected during the first L rounds of the execution, and It measures packet latency of only these packets, while it is kept injecting packets after the round L until all the packets injected in the first L rounds have been heard on the channel, and then we terminate the simulating execution. This parameter L is a reasonably large positive integer, like L = 100,000.
We need to relate outcomes of experiments to theoretical bounds on packet latency. Such bounds are in the literature for the cases of static adversaries and for dynamic 1activating adversaries. Here one may notice that the known three deterministic algorithms for the dynamic 1activating adversaries can handle injection rates up to 1/2 or less, see [1]. We expect that fixed set of nodes should have a stabilizing effect on executions of a broadcast algorithm.
Conjecture 1 The three adhoc algorithms for the 1activating adversary provide bounded packet latency for each injection rate smaller than 1 in the static model, that is, when there is a fixed set of nodes.
If this conjecture holds true, then the plots of the respective bounds could be used in charts to relate outcomes of experiments to these very theoretical bounds on packet latency as the simulations will be for 1activating static randomized adversary.
18
5.1 Specific Experiments
There are five deterministic algorithms presented above. (The randomized algorithms interest us only as point of reference in comparisons with deterministic algorithms.) For each of them we should have a theoretical bound on packet latency, say worstcase, then It may measure, say, both worst case or average packet latency in a simulation of the randomized adversary. To obtain a chart, it may plot the corresponding three curves for different injection rates, say for injection rates that are multiples of 1/20. These are the simplest experiments in which one looks at each algorithm independently and compare the theoretical bounds to the bounds obtained through simulations.
More involved experiments will be about comparing different algorithms. For example, deterministic agains randomized, to verify advantages and disadvantages of their designs. Such comparisons may be determined by having parameters of the system vary: injection rate, number of stations, burstiness, etc, while keeping the others constant. A chart will have one curve for an algorithm, say representing worstcase packet latency as measured while simulating the suitable randomized adversary.
19
5.1.1 Deterministic Distributed Algorithms
Next we we present outcomes of experiments of deterministic algorithms.
0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
Injection Rate
Figure 5.1: Algorithm RRW. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? = 100,000; n = 200; 6 = 20.
Figure 5.1 and Table 5.1 on page 21 present outcomes of simulations for the deterministic algorithm Round Robin Withholding (RRW). It is found the average latency, maximum packet latency and upper bounds (wrostcase) with different number of injection rates and parameters: L = 100,000; n = 200; b = 20; we could see when injection rate increases, the number of packets that injected per round are increasing also. At the beginning we can notice that when injection rate was 0.05, the values are closed for each other because the number of packets that inject each round are very small. For the middle injection rate like 0.5 the values of latencies are becoming approximately double for each other respectively. At the high injection rate like 0.95 the maximum latency becomes about triple bigger than average value, but the theoretical bound becomes approximately 31 times bigger than maximum latency and about 70 times than average latency.
20
Table 5.1: Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values: R = 100, 000; n = 200; b = 20.
Average Packet Latency Maximum Packet Latency Upper Bounds (WorstCase)
105 216 244
111 234 272
114 250 304
123 260 344
131 282 391
139 302 449
150 328 521
162 352 611
176 384 727
193 426 880
213 468 1086
237 518 1375
271 598 1796
311 696 2444
369 811 3520
443 990 5500
572 1239 9778
796 1758 22000
1228 2785 84000
21
7000
Figure 5.2: Algorithm MBTF. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? = 100, 000; n = 20; b = 8.
Figure 5.2 represents outcomes of experiments of the deterministic algorithm MoveBigToFront (MBTF). We conclude that the average latency, maximum latency and theoretical bound for each injection rate with parameters: L = 100, 000; n = 20; b = 8. We can observe that when injection rate is very low like 0.05, the average and maximum latency could see them in close values then they they still closed together while the upper bound gradually increasing until 0.5. After that upper bounds (worstcase) goes high because number of packets that injected are high and this algorithm needs time to seek for station that has packets no less than n (number of stations), it is effective with high injection rates. Another observation is which average packet latency is no more than 100 rounds that is because the burstiness and number of station are small. Indeed, this deterministic algorithm is slower than RRW.
22
Injection Rate
Figure 5.3: Algorithm SRR. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? = 100, 000; n = 200.
Figure 5.3 is about algorithm SSR. It gives the maximum packet latency and worstcase upper bound without average latency because it is very small and close to 0. Here the parameters that are used: L = 100, 000; n = 200; b = 20 with varying injection rates; I see that the maximum latency is increasing slowly; however, the theoretical bound started higher than the maximum packet latency then it goes very big. Additionally, when the injection rate close to 1 the maximum latency with this algorithm is around the number of stations that maybe because the binary search that is applied in this algorithm. We can see that this algorithm has smaller packet latency than RRW and MBTF.
23
Injection Rate
Figure 5.4: Algorithm OFRRW. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? = 100, 000; n = 50; b = 8.
Figure 5.4 is about a deterministic algorithm OFRRW. It gives the average latency, maximum packet latency and upper bounds (worstcase) with different number of injection rates with parameters: L = 100, 000; n = 50; b = 8; here we reduced the number of stations rather than I used with RRW.
We can see that when injection rate increases, the number of packets that injected per round are increasing too. At the beginning we can notice that when injection rate is 0.05, the maximum latency is three times bigger than the average ,and upper bound is six times bigger the the average latency and so on where each step that the injection rate increased the different among them is triple times. We can conclude that this algorithm is slower than RWW and SRR, but it is faster than MBTF in the settings mentioned. If we play with number of stations, we could get different observation; we will see that.
24
Injection Rate
Figure 5.5: Algorithm OFSRR. Observed values of average, maximum packet latency and worstcase for varying injection rates. Parameter values:/? = 100, 000; n = 50; b = 8.
Figure 5.5 is about a deterministic algorithm OFSRR. Flere It is applied the same setting for OFRRW. It followed the same behavior of OFRRW where the average packet latency, maximum latency started very small while the worstcase is started high because OFSRR and OFRRW have the same theoretical bounds. Finally, observe that this algorithm has smaller packet latency than SRR and RRW while it similar in this respect to OFRRW, but it is faster than MBTF.
25
7000
Figure 5.6: Seven deterministic algorithms. Observed values of maximum packet latency for varying injection rates. Parameter values:/? = 100, 000; n = 20; b = 20.
Figure 5.6 compared seven deterministic distributed algorithms two backoff ones and other five to see which algorithm is better and which one is the worst among all deterministic protocols. We can observe that SearchRoundRobin algorithms is the faster among all deterministic algorithms while CountingBackoff is the slower protocol.
26
5.1.2 Randomized Versus Deterministic Distributed Algorithms
We tested the randomized algorithms BinaryExponentialBackoff and QuadraticBackoff in simulations similarly as deterministic distributed algorithms, with varying injection rates with parameters: R = 100, 000; n = 20; b = 20.
Injection Rate
Figure 5.7: Randomized algorithms. Observed values maximum packet latency for varying injection rates. Parameter values:/? = 100, 000; n = 20; b = 20.
Figure 5.7 presents outcomes of experiments for th=wo kinds of backoff algorithms: exponential and quadratic. We can notice that the maximum latency are very closed together when the injection rate less than 0.35 while after the injection rate increased the maximum latency for algorithm BinaryExponentialBackOff goes higher than QuadraticBackOff protocol. We can notice that algorithm QuadraticBackOff is the winner when we compare as randomized protocols; however, SearchRoundRobin algorithm is the winner and BinaryExponentialBackOff is the worst among all algorithms that considered in this thesis with varying injection rates.
27
Injection Rate
Figure 5.8: Three deterministic algorithms. Observed values of maximum packet latency for varying injection rates. Parameter values:/? = 100, 000; n = 20; b = 20.
We discovered that the maximum packet latency with the same setting that are
used in randomize algorithms in Figure 5.8 to see the differentness among all non
randomize and randomize algorithm by using the parameter maximum latency.
We conclude that MBTF is the slower one than all others protocol and Binary
ExponentialBackoff and QuadraticBackoff should very fast algorithms rather than
with others; however, in general, the QuadraticBackoff is the faster one.
28
Injection Rate
Figure 5.9: Four Backoff algorithms. Observed values of maximum packet latency for varying injection rates. Parameter values:/? = 100, 000; n = 80; b = 20.
Figure 5.9 depicts measured maximum packet latencies for four distributed Backoff protocols with varying injection rates. As we can see that counting protocol is so faster one among them and still BinaryExponentialBackoff is the slowest one while QuadraticBackof and CountingBackoff are in between then QueueBackoff is the winner in this respect. As mentioned before when the injection rate is large, the the packet latency for BinaryExponentialBackoff algorithm is too large.
29
5.1.3 Varying Burstiness
We consider another scenario of varying burstiness with fixed number of stations, rounds and injection rate.
5 10 15 20 25 30 35 40 45 50
Burstiness
Figure 5.10: Three deterministic algorithms. Observed values maximum packet latency for varying Burstiness. Parameter values:/? = 100, 000; n = 10; injection rate is 1.
Figure 5.10 considers a small number of stations. Then MBTF is beaten while RRW is winner. That means MBTF is more sensitive by number of stations, but RRW is more sensitive by burstiness. SRR appears to combine sensitively to the number of stations and burstiness.
30
5.1.4 Varying Numbers of Stations
This section is illustrated different number of stations with fixed burstiness, rounds and injection rate=0.75 to figure out the maximum packet latency for some deterministic and randomized algorithms.
Figure 5.11: Observed values maximum packet latency for varying number of stations. Parameter values:/? = 100, 000; b = 20; injection rate = 0.75.
Figure 5.11 demonstrated how MBTF is beaten because this protocol is more effective with number of stations while RRW affects by number of stations, burstiness and injection rate. We can see that SRR here becomes the winner because I fixed number of burstiness, rounds, and injections. It is more sensitive by how many packets that injected in each stations; also it is effective by number of stations, but more sensitive with injection rate and maximum packets that could inject per round.
31
Figure 5.12: Observed values maximum packet latency for varying number of stations. Parameter values:/? = 100, 000; b = 20; injection rate = 0.75.
The randomized protocols are also effective by different number of stations as we can see in the Figure 5.12 with above settings setup that maximum latency for BinaryExponentialBackOff and QuadraticExponentialBackOff algorithms are increased high concurrently the number of stations are increased, but, in general the deterministic protocols are winner in order to compare them with randomized when applied to this scenario.
32
5.2 Throughput
In this section is found the number of packets that are injected and number of packets that are sent; it is another way to check the performance of each algorithm. The settings that used to figure out these numbers are n = 200; b = 20, L = 100, 000; A = p/0.3.
Table 5.2: Throughput
Algorithm Packets Injected Packets Sent Packets Injected Packets Sent
(p=0.05) (p=0.05) (p=0.995) (p=0.995)
RRW 5019 5013 99519 95456
SRR 10037 5019 199037 99518
MBTF 10036 5012 199037 92648
OFRRW 5018 5018 99518 96085
OFSRR 5019 4590 99619 48666
BEB 4915 4915 96764 56668
QEB 4928 4928 97218 35396
Table 5.2 summarizes the outcomes of experiments which reflect how each protocol works under low and high injection rates. We can notice that algorithm RoundRobinWithholding and OldFirstRoundRobinWithholding perform comparatively well. The efficiency is approximated about 99% for RRW and OFRRW. SearchRoundRobin and MoveBigToFront efficiency are about 50% because it sent about half packets that are injected in both high and low injection rate. The throughput of algorithm OldFirstRoundRobinWithholding is about 98% when the injection rate is low while the throughput is about 51% when the injection rate is high. Finally, the
randomized protocols are doing perfect throughput when set low injection rate where
33
the efficiency for them is 100%; on the other hand, when we applied high injection rate algorithm BinaryExponentialBackOff throughput is approximately 58% while algorithm QuadraticExponentialBackOff is about 36%.
5.3 Future Work
We considered p = A when generating packets per round because. This is only one of possible approaches to create a simulation environment related to worstcase adversarial models.
For future work to improve this project or to get different outcomes by assuming A is a injection rate and p is closed to 1 then see what will get from these changes. Another way to generate packets each round assumes that A is very close to p, but it is more than p. It assumes that because we need to keep bucket nonempty and nonfull like something in between to guarantee that the simulation could injection number of packets each round without idle or busy. In addition, it considered that the randomized adversarial injections model can activate at most one station per round. There is another way we could modify this approach that the model of adversary could activate more than one station per round. This change should give us different results by measuring packet latency or other factors. Furthermore, it can consider other deterministic and distributed protocols and simulate them and compare their outcomes. This type of study accepts many assumptions and suggestions to generate packets or the way that the adversarial injection model simulates or techniques to activate station
34
CHAPTER VI
CONCLUSION
We proposed an adversarial model, called randomized leaky bucket adversary, that is amenable to simulations. It is determined by three parameters: injection rate, burstiness, and a parameter of a Poisson distribution. In simulations, it was always a 1activating static adversary, which means at most one station was activate per round.
We simulated five distributed deterministic protocols RoundRobinWithholding (RRW), OlderFirstRoundRobinWithholding (OFRRW), SearchRoundRobin (SRR), OlderFirstSearchRoundRobin (OFSRR), and MoveBigToFront (MBTF). The maximum packet latency and average latency was compared with the upper bounds (worst case) for each algorithm. This allows to see the behavior of each algorithm when the parameters of the environment vary, like injection rates or the numbers of stations.
The simulations included two randomized algorithms BinaryExponentialBackoff (BEB) and QuadraticBackoff (QB). The backoff protocols are considered in their windowed versions. They operate under the principle that a station tries to transmit the packets in the order of their injection, and when a new packet is available then the node selects a round uniformly at random in the current window and then waits for this round to occur and transmits the packet. The goal was to investigate by simulating these protocol is to compare them with five deterministic protocols mentioned above.
The result that got are reflecting the behavior of each algorithm. When the number of stations is a big as 200 and the burstiness gets fixed, with 19 incremented injection rates, MBTF is the beaten one while SRR is the winner among them because MBTF protocol is more sensitive with number of stations.
We carried out a comparative study among randomized and deterministic algo
35
rithms to see which is faster and which is slower by using same settings for all of them and measuring the maximum packet latency for each. We observed that when the set 10 stations and fixed the burstiness with 19 varying injection rates, BEB is the beaten and SRR is the winner. Here MTTF becomes the winner compared with other deterministic protocol because of the small number of stations we can say that a big observation.
Furthermore, we considered the maximum latency for randomized and deterministic protocols for different numbers of stations and fixed the injection rate to be 0.75 and burstiness to be 20. It turned out that CountingBack performed worst among all considered deterministic algorithms when the injection rate increased. For randomized protocols, they are also sensitive with number of stations where the maximum latency for algorithm BinaryExponentialBackoff (BEB) increased higher than the maximum packet latency for algorithm QuadraticBackoff (QB). Indeed, with different number of station the BEB is the slower protocol among all algorithms that are considered in this project while algorithm SearchRoundRobin is the faster one among them.
36
REFERENCES
[1] Lakshmi Anantharamu and Bogdan S. Chlebus. Broadcasting in ad hoc multiple access channels. Theoretical Computer Science, 584:155176, 2015.
[2] Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Deterministic broadcast on multiple access channels. In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), pages 15, 2010.
[3] Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Medium access control for adversarial channels with jamming. In Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 6796 of Lecture Notes in Computer Science, pages 89100. Springer, 2011.
[4] Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Packet latency of deterministic broadcasting in adversarial multiple access channels. CoRR, abs/1701.00186, 2017.
[5] Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Frank Thomson Leighton, Zhiyong Liu, and Jon M. Kleinberg. Universalstability results and performance bounds for greedy contentionresolution protocols. Journal of the ACM, 48(1):3969, 2001.
[6] Matthew Andrews and Lisa Zhang. Routing and scheduling in multihop wireless networks with timevarying channels. In Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 10311040, 2004.
[7] Michael A. Bender, Martin FarachColton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. Adversarial contention resolution for simple channels. In Proceedings of the 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 325332, 2005.
[8] Daniel S. Berger, Martin Karsten, and Jens Schmitt. On the relevance of adversarial queueing theory in practice. SIGMETRICS Perform. Eual. Reu., 42(l):343354, June 2014.
[9] Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P. Williamson. Adversarial queuing theory. Journal of the ACM, 48(1): 1338, January 2001.
37
[10] Bogdan S. Chlebus. Randomized communication in radio networks. In Panos M. Pardalos, Sanguthevar Rajasekaran, John H. Reif, and Jose D. P. Rolim, editors, Handbook of Randomized Computing, volume I, pages 401456. Kluwer Academic Publishers, 2001.
[11] Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Maximum throughput of multiple access channels in adversarial environments. Distributed Computing, 22(2):93116, 2009.
[12] Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Adversarial queuing on the multiple access channel. ACM Transactions on Algorithms, 8( 1):5:15:31, 2012.
[13] Robert G. Gallager. A perspective on multiaccess channels. IEEE Transactions on Information Theory, 31 (2): 124142, 1985.
[14] Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson. A bound on the capacity of backoff and acknowledgmentbased protocols. SIAM Journal on Computing, 33(2):313 331, 2004.
[15] Johan Hastad, Frank Thompson Leighton, and Brian Rogoff. Analysis of backoff protocols for multiple access channels. SIAM Journal on Computing, 25(4):740774, 1996.
[16] Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395404, 1976.
[17] Michael Mitzenmacher and Eh Upfal. Probability and Computing. Cambridge University Press, Second edition, 2017.
[18] Prabhakar Raghavan and Eh Upfal. Stochastic contention resolution with short delays. SIAM Journal on Computing, 28(2):709719, 1998.
[19] Sheldon M. Ross. Simulation. Elsevier, Fifth edition, 2013.
38

Full Text 
PAGE 1
ACOMPARATIVESTUDYOFBROADCASTINGONMULTIPLEACCESS CHANNELS by MUSTAFAA.ALKHAFAJI B.S.,ThiQarUniversity,2011 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof MasterofScience ComputerScienceProgram 2017
PAGE 2
This thesis for the Master of Science degree by Mustafa A. Alkhafaji has been approved for the Computer Science Program by Bogdan S. Chlebus, Farnoush BanaeiKashani Ellen Gethner December16,2017 ii
PAGE 3
Alkhafaji, Mustafa A. (M.S., Computer Science Program) A Comparative Study of Broadcasting on Multiple Access Channels Thesis directed by Bogdan S. Chlebus ABSTRACT We study broadcasting on multiple access channels by deterministic distributed algorithms. Packet injections are determined by adversarial models. The power of a worstcase adversary is constrained by the rate of injection and a bound on the number of dierent packets that could be injected in one round. We propose models of packet injections that conform to worstcase adversarial constraints but have stochastic components that can be simulated. We implement and simulate a number of deterministic and randomized broadcast algorithms. The performance of broadcast algorithms is measured by packet latenc y We compare various broadcast algorithms by their performance in simulations. The form and content of this abstract are approved. I recommend its publication. Approved:BogdanS.Chlebus iii
PAGE 4
DEDICATION Idedicatethisworktomyparents,andtomywholefamilywhohavesupportedme throughoutthetimeofthisworkandmotivatedmetochallengethedicultiesoflife andbecomethepersonwhoIam. iv
PAGE 5
ACKNOWLEDGMENTS IwanttothanktheHigherCommitteeofEducationDevelopmentinIraqHCED forsupportingmystudiesattheUniversityofColoradoDenver. SpecialthanksgotomyadvisorBogdanChlebusforhisguidancethroughthis work. IowemanythankstomydearfriendMohammedQasimforhisencouragement andadvice. v
PAGE 6
TABLEOFCONTENTS INTRODUCTION............................... 1 RELATEDWORK............................... 3 TECHNICALPRELIMINARIES.......................6 BROADCAST ALGORITHMS . . . 13 4.1 DistributedDeterministicAlgorithms.................14 4.2 AdhocDeterministicAlgorithms....................16 4.3 Randomized Algorithms . . . 17 THEMETHODOLOGYOFEXPERIMENTS................18 5.1 SpecifcExperiments.......................... 19 5.1.1 DeterministicDistributedAlgorithms..............20 5.1.2 RandomizedVersusDeterministicDistributedAlgorithms.. 27 5.1.3 VaryingBurstiness....................... 30 5.1.4 VaryingNumbersofStations.................. 31 5.2Throughput............................... 33 5.3FutureWork...............................34 CONCLUSION................................. 35 REFERENCES...................................37 vi
PAGE 7
LISTOFTABLES Table 5.1Observedvaluesofaverage,maximumpacketlatencyandworstcasefor varyinginjectionrates.Parametervalues: R =100 ; 000; n =200; b =20.21 5.2Throughput..................................33 vii
PAGE 8
LISTOFFIGURES Figure 5.1AlgorithmRRW.Observedvaluesofaverage,maximumpacketlatencyandworstcaseforvaryinginjectionrates.Parametervalues: R = 100 ; 000; n =200; b =20............................20 5.2AlgorithmMBTF.Observedvaluesofaverage,maximumpacketlatencyandworstcaseforvaryinginjectionrates.Parametervalues: R = 100 ; 000; n =20; b =8.............................22 5.3AlgorithmSRR.Observedvaluesofaverage,maximumpacketlatencyand worstcaseforvaryinginjectionrates.Parametervalues: R =100 ; 000; n = 200.......................................23 5.4AlgorithmOFRRW.Observedvaluesofaverage,maximumpacketlatencyandworstcaseforvaryinginjectionrates.Parametervalues: R = 100 ; 000; n =50; b =8.............................24 5.5AlgorithmOFSRR.Observedvaluesofaverage,maximumpacketlatencyandworstcaseforvaryinginjectionrates.Parametervalues: R = 100 ; 000; n =50; b =8.............................25 5.6Sevendeterministicalgorithms.Observedvaluesofmaximumpacketlatencyforvaryinginjectionrates.Parametervalues: R =100 ; 000; n = 20; b =20....................................26 5.7Randomizedalgorithms.Observedvaluesmaximumpacketlatencyfor varyinginjectionrates.Parametervalues: R =100 ; 000; n =20; b =20 : .27 5.8Threedeterministicalgorithms.Observedvaluesofmaximumpacketlatencyforvaryinginjectionrates.Parametervalues: R =100 ; 000; n = 20; b =20....................................28 5.9FourBackoalgorithms.Observedvaluesofmaximumpacketlatencyfor varyinginjectionrates.Parametervalues: R =100 ; 000; n =80; b =20..29 5.10Threedeterministicalgorithms.Observedvaluesmaximumpacketlatency forvaryingBurstiness.Parametervalues: R =100 ; 000; n =10;injection rateis1.....................................30 5.11Observedvaluesmaximumpacketlatencyforvaryingnumberofstations. Parametervalues: R =100 ; 000; b =20;injectionrate=0 : 75........31 5.12Observedvaluesmaximumpacketlatencyforvaryingnumberofstations. Parametervalues: R =100 ; 000; b =20;injectionrate=0 : 75........32 viii
PAGE 9
CHAPTER I INTRODUCTION A multiple access channel is a formal model of of a broadcasting environment. It is an abstraction of the Ethernet [16], which is the most popular implementation of local area networks. There are a number of nodes (stations) attached to a channel. Multiple soverlapping transmissions result in an interference, which is also called a collision for access to the transmitting medium. The semantics of multiple access channels is defned by two properties: (1) when one station transmits then the message is heard by all the stations. (2) multiple overlapping transmissions collide with each other and none is heard on the channel. We consider the slotted model of a channel in which an execution of a broadcast algorithm is partitioned into rounds, so that it take a round to transmit one message and multiple messages transmitted in the same round result in a collision. We discuss and compare distributed broadcast algorithms when packets are injected continuously into stations. The numbers of packets injected into the stations are constrained by a leakybucket adversarial model [1, 5, 9, 11, 12]. The adversarial model which provides an upper bound on the amount of generated trac is determined by two parameters: injection rate and burstiness, and is understood as is known as a leakybucket adversarial model. Packet injection denotes an upper bound on the average number of packets injected per round, averaged over all possible time intervals. Burstiness is defned as the maximum number of packets that can be injected in a round. The simulations we design constrain the number of packets generated such that they always conform to an adversary with some injection rate and burstiness b. Packets are initially generated with a suitable Poisson distribution, which has its 1
PAGE 10
parameter adjustedto .Thistogethergivesthreeparameters: ;;b Thenumberofstationsthatattachedtothechannelisxedandtheirnumber n isknown,inthatitcanbeusedincodesofalgorithms.Stationsaresuppliedwith privatequeues,inwhichtheycanstorepacketsuntiltheyareheardonthechannel. Theperformanceofbroadcastalgorithmsismeasuredbypacketlatency.Itcould beunderstoodeitherintheworstcase,forasuitableadversarialmodel,orinthe averagesense,subjecttostipulationsofpacketinjectionthatinvolvesrandomization inpacketgeneration. Thetraditionalalgorithmicapproachtobroadcastonmultipleaccesschannelsin adistributedmannerusesrandomizationtoarbitrateforaccesstothechannel.Such randomizedalgorithmsincludebackoprotocols,suchasthebinaryexponential backousedintheEthernet[16]suiteoftechnologies. Recently,deterministicbroadcastalgorithmswereproposedandshowedtohave boundedpacketlatencyintheworstcaseinadversarialmodelsdeterminedbyinjectionrateandburstiness.Wesimulatebothdeterministicalgorithmsandrandomized ones. Thethesiscomparesvariousalgorithmsthroughsimulations.Thetheoretical worstcaseupperboundsonpacketlatencyarecomparedtoboundsobtainedinsimulations,bothaverageandmaximum. 2
PAGE 11
CHAPTER II RELATED WORK There is an rich literature on algorithms for multiple access channels, see the surveys [10, 13]. The methodology of adversarial queuing was considered extensively in the literature [7, 8, 9, 11, 12]. Some studies that related with this types of project is considered packet routing when packets are injected continuously into a network. They evolved an adversarial theory of queuing reached at addressing some of the limitations queuing theory based on fxedtime constant generation and origin in probabilistic analysis. They test the stability and reliability of queuing networks and behavior when the arrival data are adversarial [9] Anantharamu and Chlebus [1] study broadcast in multiple access channels in dynamically adversary form. There is an unlimited bound provide of stations that don't have names attached to a synchronous channel. There is an adversary that injects packets into stations to be broadcast on the channel. The adversary is constrained by burstiness, injection rate, and by number of passive stations that can be concurrently activated by providing them packets. They consider deterministic distributed broadcast algorithms, who are further classifed by their attributes. They show for which injection rates can algorithms investigate bounded packet latenc y when adversaries are determined to be able to activate at most one station per round. The rates of algorithms they introduce make the increasing sequence consisting of 1 = 3, 3 = 8 and 1 = 2 give a picture of the additional properties of algorithms. Also, they show that injection rate 3/4 couldn't be handled with bounded packet latenc y Most previous work on broadcasting on multiple access channel has been carried out assuming that randomization has related part to play with. When packets are created subject to stochastic limitations, randomness can aect on the status of protocols either activel y by being a part of the mechanism of a randomized protocol, 3
PAGE 12
orpassively.Therandomizeenvironmentasapartofitsspecicationdeterminedin suchawaycanberepresentedasaMarkovchainsothatstabilitycouldbeunderstood asergodicity.Fortherecentworkonthealgorithmicofrandomizedbroadcastingon multipleaccesschannels,see[14,18]. AndrewsandZhang[6]developedschedulingandroutinginwirelessnetworks whereeachnodecanbetransmiteddatatoatmostoneneighboringnodepertimeslot. Furthermore,transmissionratesanddataarrivalsaregovernedbyanadversary.They generatedschedulingalgorithmsthatensurenetworkstabilityforthecaseinwhich theadversaryspeciesthelinksthatthedatamusttransmissionthrough.Bender[7] appliedadversarialapproachtostudytheissueofproductivityofrandomizedbacko formultipleaccesschannelsinthequeuefreemodel. Injectionrateisdenedasthelargeaveragenumberofmessagesgeneratedin acategoryofslotsofrounds.Burstinessisthemaximumnumberofpacketsan adversarycouldinjectinaround.Therearetworegularmodelsofadversariesin adversarialqueuing.Whenthereisnolimitationimposedonintervalstimetoaverage packets,thenthiscategoryofadversariesiscalledleakybucket.Ifweaverageonly overintervalsofaconstantlength,thenitiscalledwindowsize;suchadversariesare ofwindowtype.Intheconceptofadversarialqueuing,windowadversarieswererst usedby[9]andleakybucketadversariesby[6] Anantharamuetal.[3]proposedhowtocomparedynamicbroadcastingversus adversariesthatareunboundedinthesensethattheycaninjectpacketsintorandomlystationswithnorestrictionsontheirnumbersnorratesofinjection.They gaveadeterministicalgorithmoptimalwithrespecttostruggleperformance,when measuringeitherthemaximumqueuesizeorthetotalnumberofpacketsinthesystem.Inaddition,theyshowedthatthealgorithmisstochasticallyoptimalforany expectedinjectionratesmallerthanorequalto1. Anantharamuetal.[4]studiedbroadcastingonmultipleaccesschannelswith 4
PAGE 13
jamminganddynamicpacketarrivals.Thecommunicationplatformisrepresented byadversarialmodelswhichspecifyrestrictsonpacketarrivalsandjamming.They considerdeterministicdistributedbroadcastalgorithmsandgiveupperboundson theworstcasepacketlatencyandthenumberofqueuedpacketsthatrelatingto thedeningadversaries.Packetarrivalsarespeciedbynumberofpacketsthatcan arriveinoneroundandtherateofinjections.Jammingislimitedbythenumberof consecutiveroundsthatcanbejammedandbytheratewithwhichtheadversary canjamrounds. 5
PAGE 14
CHAPTER III TECHNICAL PRELIMINARIES A multiple access channel is a broadcast network that allows for each node to transmit its message to all the other nodes in one round. We consider such synchronous networks when executions of communication algorithms are structured as a series of rounds. It is assumed that a multiple access channel consists the communication medium and some nodes connected to it. Nodes that have packets to transmit are called active and otherwise they are passive. The set of nodes may be considered to be either static or dynamic, depending on our preference of the model. In the static model, there is a fxed set of some n nodes. In this case, the nodes usually have fxed names that identify them, which are unique integers in the range [0 ; n )Tj/C0_0 11.955 Tf9.277 0 Td<0001>Tj/T1_1 11.955 Tf2.319 Tw 1.778 0 Td(1]. In the dynamic case, nodes may join and leave the system, they do not have fxed names, and only active nodes execute a broadcast algorithm while passive nodes are neutral. There is an unbounded supply of passive nodes in the dynamic model, and a packet may be injected into a passive node, which immediately becomes active. It is said that a node hears a transmission when it receives it successfull y The critical property of multiple access channels is how multiplicity of concurrent transmissions aects hearing messages.In general, there are three possible cases of relevant multiplicities of transmissions in a round: no nodes transmit, exactly one node transmits, and multiple (more than one) nodes transmit.When multiple nodes transmit in a round then this is referred to as a collision occurring in this round. When no node transmits in a round then the channel is silent, which is rerected by the corresponding silence feedback received from the channel by each node. When only one node transmits then all the other nodes that are actively participating in the execution hear the transmitted message, which is the feedback they receive from 6
PAGE 15
thechannel.Whenmultiplenodestransmitinthesameroundthenthiscreatesa collision,totheeectthatthemessagesinterferewitheachotherandnonecanbe heardbyanyattachednode.Inthiscase,theattachednodesheara collisionsignal asthefeedbackfromthechannel. Multipleaccesschannelscomeintwovariants,whicharedeterminedbythefeedbackobtainedfromthechannelwhenamessageisnotheard.Thechannel without collisiondetection hasthepropertythatthesilenceandcollisionsignalsareidentical,whileinthechannel withcollisiondetection theyaredierent,sothenodescan distinguishbetweenthetwocorrespondingcases.Thefeedbackobtainedfromthe channelinarounddoesnotdependwhatanodedoesinthisround;inparticular,a transmittingnodeandapausingnodereceivethesamefeedback,andifamessageis heardthenthetransmittingnodehearsthemessageaswell. Weconsiderdynamicbroadcastingwhenpacketsareinjectedbyadversaries.Varioustypesofadversariesconsideredinthispaper,theyareallspecializationsofthe leakybucketadversarialconcept.Aleakybucketadversaryisdeterminedbythefollowingtwokeynumericparameters.Oneis injectionrate ,denoted ,whichisareal numbersatisfying0 < 1.Theotheris burst component,denoted b ,whichisa positiveinteger.Togethertheymakethe type ;b oftheadversary. Ineachround,theleakybucketadversaryoftype ;b injectsanumberofpackets,whichcanbevisualizedasoccurringintwostages:rstthenumberofnew packetstobeinjectedisdeterminedfortheround,andthenthesemanypackets areinjectedintosomenodes.Thetypeofaleakybucketconstrainsthenumbersof packetsinjectedineachroundasfollows:foreachcontiguoustimeinterval of j j rounds,thenumberofpacketsinjectedintothesystemduringtheroundsin isat most j j + b Thiscapturestwopostulatesfortheadversaryoftype ;b ,thatitconstraints boththeaveragenumberofinjectedpacketsinlargeintervalsandalsotheburstsof 7
PAGE 16
packetsinjectedinsmallintervals.Indeed,theinjectionrate canbeinterpretedas theaveragenumberofpacketsinjectedinaroundwhenaveragingoverlargeintervals. Also,atmost b + b c newpacketscanbegeneratedinoneround,becausethenumber ofnewpacketsisanonnegativeintegerand j j + b = + b with j j =1. Onemayconsidervariantsofadversarialmodelsdenedbywherethenewpackets areinjected,aftertheirnumberhasbeendecidedoninaround.Thisnaturally dependsonwhethertheadversaryis static ,whichappliesforthestaticmodelofa xedsetofnodes,oritis dynamic andsomycreatenewactivenodesandaddthem tothesystem.Historically,themoststudiedcasewasofstaticadversarieswithno restrictionsonwhichnodesobtainthenewlygeneratedpackets.Alackofrestrictions meansthattheadversaryistomodelanenvironmenttostudyworstcaseperformance ofalgorithms.Thisadversarialmodelwasconsideredin[2,3,4,11,12]. Theadversarialmodelmayadditionallyrestrictthenumberofpassivenodesthat areactivatedinaround.Atmost b + b c passivenodescanbeactivatedinaround becauseeachactivationrequiresatleastonepacket. Anupperbound k onthenumberofstationsthatcanbeactivatedinaround canbeconsideredanindependentparameteroftheadversary,whichisthencalled k activating .Inparticular,AnantharamuandChlebus[1]considered1activating dynamicadversaries.Whenwerefertoanadversaryasstaticordynamiconly, withoutspecifyingaboundonnumberofactivatednodes,thenthismeansthatno restrictiononthenumberofactivationsperroundapplies,exceptforthebound b + b c Inthisthesis,itisemphasizedon1activatingstaticadversaries.Themotivation foractivatingatmostonenodeinaroundcomesfromtherealworldapplications whenmultipleaccesschannelsmodellocalareanetworksandisasfollows.Itexpects thatnodesthatareactiveusuallyhavemultiplepacketstobroadcast,sonewpackets aretypicallyinjectedintonodesthatarealreadyactive.Italsoexpectsthatnodes 8
PAGE 17
thatarepassivestaysuchthroughtheround,althoughrarelyapassivenodegets activatedandgeneratespacketstobroadcast.Thislatterinterpretationmeansalso thathavingmultiplepassivenodesactivatedinaroundissucharareeventthenit canbedisregardedwithoutdistortingtheperformanceofbroadcastingasmodeledin simulations.Theadditionaladvantageof1activatingadversariesisthatitispossible tobroadcastinadistributeddeterministicmannerwithboundedpacketlatencyfor positiveinjectionrates,againstsuchadversaries,evenindynamicsystems,aswas shownbyAnantharamuandChlebus[1]. Analternativetoadversariesconducivetostudyingworstcaseperformance,It canbuildrandomnessintoanadversarialmodel,whichallowstocapturetheaverage performance.Itreferstosuchadversariesas randomized onesandifrandomnessis notusesinanymannerthentheadversaryis worstcase .Arandomizedleakybucket adversaryisagaindeterminedbyitstype ;b .Randomnesscanaectthebehavior ofrandomizedleakybucketadversariesintwoways:intheprocessofdeterminingthe numberofpacketsinjectedinaround,andinselectingnodeswherethepacketsare injected.Eachrandomizedadversarycanalsohaveanupperboundonthenumber ofstationsactivatedinaroundasanadditionalparameter. NowItdenes randomizedleakybucketadversaries oftype ;;b ,where0 < 1and0 < .Firstwespecifyhowtodeterminethenumberofpacketsinjected inaround.Let D beavariablewhichwecallthe bucket .Itspurposeistoremember therecentinjectionsofpacketsanditisinterpretedasfollows: b D c isthemaximum numberofpacketsthatcanbeinjectedinthecurrentround. Initially, D issetto b .Thenumberofpacketsinjectedinagivenroundbythe randomizedleakybucketadversaryisdeterminedasfollows. Firstbucketisupgraded D byassigning D min[ D + ;b ].Thismeansthat theinequality D b isalwayssatised. Next,itisgeneratedanonnegativeinteger X withthePoissondistribution 9
PAGE 18
withparameter ,whichmeansthat Pr X = i = e )]TJ/F29 7.9701 Tf 6.587 0 Td [( i i ; foreachinteger i 0,see[17,19] Thenthenumber j ofpacketsinjectedinthisroundisdeterminedas j = min fb D c ;X g Finally, D isupdatedto D )]TJ/F18 11.9552 Tf 10.446 0 Td [(j ,whichmeansthattheinequality D 0isalways satised. Thiscompletesthemanipulationsof D inthisround. Proposition1 Whenarandomizedadversaryoftype ;;b ,injectspacketsina sequenceofconsecutiveroundsthenthenumbersofpacketsgeneratedineachround satisfytherequirementsoftheworstcaseadversaryoftype ;b ,for 0 < 1 and 0 < Proof: Itneedstoshowthattherandomizedadversaryinjectsatmost j j + b packetsineachinterval .Injectingapacketresultsindecrementing D to D )]TJ/F15 11.9552 Tf 12.539 0 Td [(1. Sothenumberofpacketsthatcanbeinjectedisaccountedforbyalltheincrements of D andtheinitialvalueof D .Thebucket D isincrementedbyatmost inthe beginningofeachroundin ,forthetotalofatmost j j duringalltheroundsin Additionally,thebucketsatises D b beforetherstroundof begins. ThePoissondistributionwithparameter hasthepropertythat E [ X ]= ,but theexpectednumberofpacketsinjectedinaroundissmallerthan because D is theadditionalupperbound. Let Y betherandomvariableequaltothenumberofpacketsinjectedinaround byarandomizedadversaryoftype ;;b .Itwouldbeinterestingtond E [ Y ] beyondtheestimate E [ Y ] < 10
PAGE 19
Forinjectionrate < 1,onecouldsimplyuse = inexperiments.Analternativewouldbetousesuch > that E [ Y ]= .Thenthecorrespondencebetween theworstcaseadversaryoftype ;b andtherandomizedadversaryoftype ;;b wouldbeevencloserthanwhatProposition1gives. Afterhavingdeterminedthenumberofpackets j toinject,Itneedstodetermine wherethe j newpacketsareinjected.Lettheadversarybe k activating,where k b b + c .Therearethedynamicandstaticecases. Firstthedynamiccase.Inagivenround,consider k new virtuallyactive nodes. Thesetofactiveandvirtuallyactivenodesmakesthesetofnodes eligible forthis round.Eachamongthenew j packetsisassignedaneligiblestationuniformlyatrandom,withassignmentsofdierentpacketsmadeindependently.Ifavirtuallyactive stationreceivesapacketthenitbecomesaddedtothesystemasactiveotherwiseit disappears. Next,thestaticcase.Let ` bethenumberofpassivenodesamongallthe n nodes. Theadversaryselectsmin f `;k g suchstationsuniformlyatrandomas virtuallyactive Inparticular,if ` = k thenallpassivenodesbecomevirtuallyactiveandif ` =0then thereisnovirtuallyactivenode.Again,thesetofactiveandvirtuallyactivenodes makesthesetofnodes eligible forthisround,andalsoeachofnew i packetsisassigned aneligiblestationuniformlyatrandom,withassignmentsofdierentpacketsmade independently. Eachexecutionofarandomizedleakybucketadversaryofagiventypesatisesthe specializationoftheworstcaseleakybucketadversaryofthistype,inthesensethat eachpatternofinjectionsofpacketssatisestheconstrainsdeningtheworstcase adversary.Itfollowsthatboundsonperformancemetricsofdeterministicalgorithms againstthedeterministicleakybucketadversaryapplytotherandomizedversionof theadversaryofthesametype. Therandomizedleakybucketadversaryofagiventypecanbesimulatedby 11
PAGE 20
generatinguniformdistributionsonniterangesandaPoissondistributionfora giveninjectionrateinterpretedastheexpectationofthisPoissondistribution. 12
PAGE 21
CHAPTER IIII BROADCAST ALGORITHMS It is mostly concerned with deterministic distributed algorithms. Such an algorithm is to perform dynamic broadcasting, in the sense that packets get injected into the nodes and the nodes have these packets heard on the channel by successful transmissions. An algorithms is activation based when a station without a packet to transmit ignores the feedback from the channel and starts participating actively only starting from a round when it gets activated by having a packet injected into it and stays such as ling as it has packets to transmit. An algorithm is full sensing when all the nodes listen to the channel at all times. The actions in a round of a node executing a full sensing algorithm or activation based when a station has a packet to transmit are as follows. The node frst either transmits a packet or pauses, as determined by its state. Then the nodes obtains the feedback from the channel, the same as all the other stations. Next, the node may have a number of packets injected into it in the round. Finall y the node performs local computation, which can be interpreted as a state transition. This involves the following actions. If packets were injected then they are enqueued in the local queue. Local variables are updated, depending on what occurred in the round up to this moment. The node decides if to transmit in the next round and if so the it builds a message to be transmitted. If the queue includes packets then the message may include a packet. A message transmitted on the channel may include at most one packet but it may consist of only control bits. An algorithm may not use control bits at all, then the messages transmitted int he course of its execution consist of only packets. An algorithm that has stations transmit messages with control bits is called adaptive. The messages in an execution of such an algorithm may consists of only control bits 13
PAGE 22
butforanonadaptivealgorithmifanodedoesnotwanttotransmitapacketthen thenodedoesnottransmitatall. Therearethreegroupsofalgorithms:deterministictokenones,deterministicad hocones,andrandomized. Algorithmsdesignedspecicallyforamultipleaccesschannelwithaxedsetof nodesattachedtothechanneleachwithauniquenamemayoperatebyhavingthe nodesexchangeatoken.Thetokenvisitinganodeallowsthenodetotransmit,which preventscollisions.Suchalgorithmscouldbecalled token ones;see[12,11,4].The otherparadigmisforenvironmentswithoutaxedsetofnamednodesattachedto thechannel,andinsteadnodesaredynamicallygeneratedandassignedtemporary implicitnames.Thisworksforasettinginwhichatmostonenewnodeisadded tothesysteminaround.Suchalgorithmscouldbecalled adhoc ones;see[1]. Multipleaccesschannelswithaxedsetofnamednodesattachedtothemaremore eectivethanchannelsexecutingadhocalgorithms,inthattheformercanhandle injectionrate1inastablemanner[11]andarbitraryinjectionratessmallerthan1 withboundedpacketlatency[3,4,2]whileadhocalgorithmscannothandleinjection ratesthatareatleast3 = 4withboundedpacketlatency[1]. Whatfollowsarebriefspecicationsofthealgorithmsthatwillbecompared inexperiments.Therearetwogroupsofalgorithms:deterministictokenonesand randomized. 4.1DistributedDeterministicAlgorithms Letusbeginwiththeconsideredtokenalgorithms.Algorithm MoveBigToFront MBTF AlgorithmMoveBigToFrontMBTFisanadaptivealgorithm forchannelswithoutcollisiondetection.Eachstationmaintainsalistofallstations initsprivatememory.Alistisinitializedtobesortedintheincreasingorderofnames ofstations.Thelistsaremanipulatedinthesamewaybyallthestationssotheir orderisthesame.Thealgorithmschedulesexactlyonestationtotransmitinaround, 14
PAGE 23
socollisionsneveroccur.Thisisimplementedbyhavingaconceptualtokenassigned tostations,whichisinitiallyassignedtotherststationonthelist.Astationwith thetokenbroadcastsapacket,ifithasany,otherwisetheroundissilent.Astation considersitselfbiginaroundwhenithasatleastnpackets;suchastationattaches acontrolbittoallpacketsittransmitstoindicatethisstatus.Abigstationismoved tothefrontofthelistanditkeepsthetokenforthenextround.Whenastation thatisnotbigtransmits,orwhenitpausesduetoalackofpacketswhileholdingthe token,thetokenispassedtothenextstationinthelistorderedinacyclicfashion. AlgorithmMBTFwasintroducedin[11]andshowedtobestableforinjectionrate 1.Itisstableforinjectionrate1andhasboundedpacketlatencyforinjectionrates smallerthan1. Algorithm RoundRobinWithholding RRW isafullsensingnonadaptive algorithmforchannelswithoutcollisiondetection.Itoperatesinaroundrobinfashion,inthatthestationsgainaccesstothechannelinthecyclicorderoftheirnames. Onceastationgetsaccesstothechannelbytransmittingsuccessfully,itwithholdsthe channeltounloadallthepacketsinitsqueue.Asilentroundisasignaltothenext station,inthecyclicorderofnames,totakeover.AlgorithmRRWwasintroduced in[12]andshowedtobeuniversal,thatis,stableforinjectionratessmallerthan1. Ithasboundedpacketlatencyforinjectionratessmallerthan1. AlgorithmSearchRoundRobinSRRisafullsensingnonadaptivealgorithm forchannelswithcollisiondetection.Itsexecutionproceedsasasystematicsweep acrossallthestationswiththegoaltoidentifythesewithpackets,withsuchsearch performedinthecyclicorder.Whenastationwithapacketisidentied,thestation unloadsallitspacketsonebyone.Asilentroundtriggersthesweeptoberesumed.We applybinarysearchtoidentifythenextstation.Thebinarysearchisimplemented usingcollisiondetection.Whenweinquireaboutasegmentofstations,thenall thestationswithpacketsthatareinthesegmenttransmitintheround.Asearch 15
PAGE 24
iscompletedbyapacketheard.Asilenceindicatesthatthesegmentisemptyof stationswithpackets.Acollisionindicatesthatmultiplestationsareinthesegment: thisresultsinhavingthesegmentpartitionedintotwohalves,withonesegment processednextimmediatelywhiletheotheroneispushedonastacktowait.A transitiontothenextsegmentoccurswhenthestackgetsempty.AlgorithmSRRis introducedby[12].Ithasboundedpacketlatencyforinjectionratessmallerthan1. Thealgorithms RRW and SRR canbemodiedbyusingtheapproachthat couldbecalledoldergorst,"whichwasintroducedbyAnantharamuetal.[2].Each ofthealgorithmshasexecutionsthatcanbeinterpretedashavingatokenthat traversesallthenodesinaroundrobinmanner.Calleachsuchacyclea phase Thepacketsthatareinjectedinaphaseareconsiderednew"duringthephase andbecomeold"whenthenextphasestarts.Inthecourseofaphase,thenew packetsareignoredandonlytheoldonesarebroadcast.Theresultingalgorithms arecalled OlderFirstRoundRobinWithholding OFRRW and OlderFirstSearchRoundRobin OFSRR ,respectively. 4.2AdhocDeterministicAlgorithms Nextwepresenttheadhocalgorithms;theyallwereproposedbyAnantharamu andChlebus[1].Algorithm CountingBackoff isanonadaptiveactivationbased algorithmforchannelswithcollisiondetection. Activenodesarestoredonavirtualstackandanactivestationremembersits distancefromthetopofthestack.Itwassownthatthealgorithmhasbounded packetlatencywheninjectionrateissmallerthan1 = 3.Finally,thereisthealgorithm QueueBackoff whichisanadaptiveactivationbasedalgorithmforthechannel withoutcollisiondetectionthathasboundedpacketlatencyforinjectionrate1 = 2. Thesetwoalgorithmsdonotusethenamesofnodes,eveniftheyavailable.The boundedpacketlatencyholdsevenwhenthereisnoxedsetofnodesattachedtothe channelandtheadversaryhasthepowertocreatenewstationsbyinjectingpackets 16
PAGE 25
intothem,butatmostonenewstationinaround. 4.3RandomizedAlgorithms Finally,itwillsimulatethebehavioroftworandomizedalgorithms.Thesearethe BinaryExponentialBackoff BEB and QuadraticBackoff QB .The backoprotocolsareconsideredintheirwindowedversions.Anodetriestobroadcast thepacketsintheorderoftheirinjection.Whenanewpacketisavailablethen thenodeselectsarounduniformlyatrandominthecurrentwindowthenwaits forthisroundtooccurandtransmitsthepacket.Therstwindowisofsize1, whichmeansthatanewpacketistransmittedimmediately.Whenatransmission isheardthenthenextpacketisprocessed,otherwisewhenthereisacollisionthen thewindowisincreasedandaroundinitisselectedfromituniformlyatrandom. For BinaryExponentialBackoff ,the i thwindowsizewasdeterminedas2 i and for QuadraticBackoff ,the i thwindowsizewasdenedtobe i 2 .wheretheround ofatransmissionisdrawnfromatimeintervaluniformlyatrandom. Thereisanoptiontoconsiderthesealgorithmswithanupperboundonthe windowsize,asbinaryexponentialbackoisusedintheimplementationoftheEthernet.Forinstance,the i thwindowsizefor BinaryExponentialBackoff could be2 min ;i ,whichisexactlyasintheEthernet,andfor QuadraticBackoff ,the i thwindowsizecouldbemin i; 32 2 .Observethatwiththesechoicesofconstants themaximumsizeofawindowisthesamein BEB and QB .Thetworandomized protocolsareproposedin[14,15,16]. 17
PAGE 26
CHAPTER V THE METHODOLOGY OF EXPERIMENTS We consider systems with a fxed number of stations attached to the channel. only the static case The number of nodes n is a parameter of a simulation. This is typically a small positive integer, say, in the range [1 ; 100]. We will consider only 1activating adversaries. The simulations will simply mimic randomized leakybucket adversaries: but only static 1activating adversaries. It needs to specify how to terminate an experiment. For example, we may designate a certain constant L as a parameter. This constant L denotes the number of rounds during which new packets are injected for which is measured packet latenc y The precise meaning of L is as follows: packets are injected during the frst L rounds of the execution, and It measures packet latency of only these packets, while it is kept injecting packets after the round L until all the packets injected in the frst L rounds have been heard on the channel, and then we terminate the simulating execution. This parameter L is a reasonably large positive integer, like L = 100 ; 000. We need to relate outcomes of experiments to theoretical bounds on packet latenc y Such bounds are in the literature for the cases of static adversaries and for dynamic 1activating adversaries. Here one may notice that the known three deterministic algorithms for the dynamic 1activating adversaries can handle injection rates up to 1 = 2 or less, see [1]. We expect that fxed set of nodes should have a stabilizing eect on executions of a broadcast algorithm. Conjecture 1 The three adhoc algorithms for the 1 activating adversary provide bounded packet latency for each injection rate smaller than 1 in the static model, that is, when there is a fxed set of nodes. If this conjecture holds true, then the plots of the respective bounds could be used in charts to relate outcomes of experiments to these very \theoretical bounds on packet latency as the simulations will be for 1activating static randomized adversar y 18
PAGE 27
5.1SpecicExperiments Therearevedeterministicalgorithmspresentedabove.Therandomizedalgorithmsinterestusonlyaspointofreferenceincomparisonswithdeterministic algorithms.Foreachofthemweshouldhaveatheoreticalboundonpacketlatency, sayworstcase,thenItmaymeasure,say,bothworstcaseoraveragepacketlatency inasimulationoftherandomizedadversary.Toobtainachart,itmayplotthecorrespondingthreecurvesfordierentinjectionrates,sayforinjectionratesthatare multiplesof1 = 20.Thesearethesimplestexperimentsinwhichonelooksateach algorithmindependentlyandcomparethetheoreticalboundstotheboundsobtained throughsimulations. Moreinvolvedexperimentswillbeaboutcomparingdierentalgorithms.For example,deterministicagainsrandomized,toverifyadvantagesanddisadvantages oftheirdesigns.Suchcomparisonsmaybedeterminedbyhavingparametersofthe systemvary:injectionrate,numberofstations,burstiness,etc,whilekeepingthe othersconstant.Achartwillhaveonecurveforanalgorithm,sayrepresentingworstcasepacketlatencyasmeasuredwhilesimulatingthesuitablerandomizedadversary. 19
PAGE 28
5.1.1DeterministicDistributedAlgorithms Nextwewepresentoutcomesofexperimentsofdeterministicalgorithms. Figure5.1:AlgorithmRRW.Observedvaluesofaverage,maximumpacketlatency andworstcaseforvaryinginjectionrates.Parametervalues: R =100 ; 000; n = 200; b =20. Figure5.1andTable5.1onpage21presentoutcomesofsimulationsforthedeterministicalgorithmRoundRobinWithholdingRRW.Itisfoundtheaveragelatency, maximumpacketlatencyandupperboundswrostcasewithdierentnumberofinjectionratesandparameters: L =100 ; 000; n =200; b =20;wecouldseewhen injectionrateincreases,thenumberofpacketsthatinjectedperroundareincreasing also.Atthebeginningwecannoticethatwheninjectionratewas0 : 05,thevalues areclosedforeachotherbecausethenumberofpacketsthatinjecteachroundare verysmall.Forthemiddleinjectionratelike0 : 5thevaluesoflatenciesarebecoming approximatelydoubleforeachotherrespectively.Atthehighinjectionratelike0 : 95 themaximumlatencybecomesabouttriplebiggerthanaveragevalue,butthetheoreticalboundbecomesapproximately31timesbiggerthanmaximumlatencyand about70timesthanaveragelatency. 20
PAGE 29
Table5.1:Observedvaluesofaverage,maximumpacketlatencyandworstcasefor varyinginjectionrates.Parametervalues: R =100 ; 000; n =200; b =20. AveragePacketLatencyMaximumPacketLatencyUpperBoundsWorstCase 105216244 111234272 114250304 123260344 131282391 139302449 150328521 162352611 176384727 193426880 2134681086 2375181375 2715981796 3116962444 3698113520 4439905500 57212399778 796175822000 1228278584000 21
PAGE 30
Figure5.2:AlgorithmMBTF.Observedvaluesofaverage,maximumpacketlatency andworstcaseforvaryinginjectionrates.Parametervalues: R =100 ; 000; n =20; b = 8. Figure5.2representsoutcomesofexperimentsofthedeterministicalgorithm MoveBigToFrontMBTF.Weconcludethattheaveragelatency,maximumlatency andtheoreticalboundforeachinjectionratewithparameters: L =100 ; 000; n = 20; b =8 : Wecanobservethatwheninjectionrateisverylowlike0 : 05,theaverage andmaximumlatencycouldseetheminclosevaluesthentheytheystillclosedtogetherwhiletheupperboundgraduallyincreasinguntil0 : 5.Afterthatupperbounds worstcasegoeshighbecausenumberofpacketsthatinjectedarehighandthis algorithmneedstimetoseekforstationthathaspacketsnolessthannnumber ofstations,itiseectivewithhighinjectionrates.Anotherobservationiswhich averagepacketlatencyisnomorethan100roundsthatisbecausetheburstiness andnumberofstationaresmall.Indeed,thisdeterministicalgorithmisslowerthan RRW. 22
PAGE 31
Figure5.3:AlgorithmSRR.Observedvaluesofaverage,maximumpacketlatency andworstcaseforvaryinginjectionrates.Parametervalues: R =100 ; 000; n =200. Figure5.3isaboutalgorithmSSR.Itgivesthemaximumpacketlatencyand worstcaseupperboundwithoutaveragelatencybecauseitisverysmallandcloseto 0.Heretheparametersthatareused: L =100 ; 000; n =200; b =20withvarying injectionrates;Iseethatthemaximumlatencyisincreasingslowly;however,the theoreticalboundstartedhigherthanthemaximumpacketlatencythenitgoesvery big.Additionally,whentheinjectionratecloseto1themaximumlatencywiththis algorithmisaroundthenumberofstationsthatmaybebecausethebinarysearch thatisappliedinthisalgorithm.Wecanseethatthisalgorithmhassmallerpacket latencythanRRWandMBTF. 23
PAGE 32
Figure5.4:AlgorithmOFRRW.Observedvaluesofaverage,maximumpacketlatency andworstcaseforvaryinginjectionrates.Parametervalues: R =100 ; 000; n =50; b = 8. Figure5.4isaboutadeterministicalgorithmOFRRW.Itgivestheaveragelatency,maximumpacketlatencyandupperboundsworstcasewithdierentnumber ofinjectionrateswithparameters: L =100 ; 000; n =50; b =8;herewereducedthe numberofstationsratherthanIusedwithRRW. Wecanseethatwheninjectionrateincreases,thenumberofpacketsthatinjected perroundareincreasingtoo.Atthebeginningwecannoticethatwheninjectionrate is0 : 05,themaximumlatencyisthreetimesbiggerthantheaverage,andupperbound issixtimesbiggerthetheaveragelatencyandsoonwhereeachstepthattheinjection rateincreasedthedierentamongthemistripletimes.Wecanconcludethatthis algorithmisslowerthanRWWandSRR,butitisfasterthanMBTFinthesettings mentioned.Ifweplaywithnumberofstations,wecouldgetdierentobservation;we willseethat. 24
PAGE 33
Figure5.5:AlgorithmOFSRR.Observedvaluesofaverage,maximumpacketlatency andworstcaseforvaryinginjectionrates.Parametervalues: R =100 ; 000; n =50; b = 8. Figure5.5isaboutadeterministicalgorithmOFSRR.HereItisappliedthesame settingforOFRRW.ItfollowedthesamebehaviorofOFRRWwheretheaverage packetlatency,maximumlatencystartedverysmallwhiletheworstcaseisstarted highbecauseOFSRRandOFRRWhavethesametheoreticalbounds.Finally, observethatthisalgorithmhassmallerpacketlatencythanSRRandRRWwhileit similarinthisrespecttoOFRRW,butitisfasterthanMBTF. 25
PAGE 34
Figure5.6:Sevendeterministicalgorithms.Observedvaluesofmaximumpacket latencyforvaryinginjectionrates.Parametervalues: R =100 ; 000; n =20; b =20. Figure5.6comparedsevendeterministicdistributedalgorithmstwobackoones andothervetoseewhichalgorithmisbetterandwhichoneistheworstamong alldeterministicprotocols.WecanobservethatSearchRoundRobinalgorithmsis thefasteramongalldeterministicalgorithmswhileCountingBackoistheslower protocol. 26
PAGE 35
5.1.2RandomizedVersusDeterministicDistributedAlgorithms WetestedtherandomizedalgorithmsBinaryExponentialBackoandQuadraticBackoinsimulationssimilarlyasdeterministicdistributedalgorithms,withvarying injectionrateswithparameters: R =100 ; 000; n =20; b =20. Figure5.7:Randomizedalgorithms.Observedvaluesmaximumpacketlatencyfor varyinginjectionrates.Parametervalues: R =100 ; 000; n =20; b =20 : Figure5.7presentsoutcomesofexperimentsforth=wokindsofbackoalgorithms:exponentialandquadratic.Wecannoticethatthemaximumlatencyare veryclosedtogetherwhentheinjectionratelessthan0 : 35whileaftertheinjection rateincreasedthemaximumlatencyforalgorithmBinaryExponentialBackOgoes higherthanQuadraticBackOprotocol.WecannoticethatalgorithmQuadraticBackOisthewinnerwhenwecompareasrandomizedprotocols;however,SearchRoundRobinalgorithmisthewinnerandBinaryExponentialBackOistheworst amongallalgorithmsthatconsideredinthisthesiswithvaryinginjectionrates. 27
PAGE 36
Figure5.8:Threedeterministicalgorithms.Observedvaluesofmaximumpacket latencyforvaryinginjectionrates.Parametervalues: R =100 ; 000; n =20; b =20. Wediscoveredthatthemaximumpacketlatencywiththesamesettingthatare usedinrandomizealgorithmsinFigure5.8toseethedierentnessamongallnonrandomizeandrandomizealgorithmbyusingtheparametermaximumlatency. WeconcludethatMBTFisthesloweronethanallothersprotocolandBinaryExponentialBackoandQuadraticBackoshouldveryfastalgorithmsratherthan withothers;however,ingeneral,theQuadraticBackoisthefasterone. 28
PAGE 37
Figure5.9:FourBackoalgorithms.Observedvaluesofmaximumpacketlatencyfor varyinginjectionrates.Parametervalues: R =100 ; 000; n =80; b =20. Figure5.9depictsmeasuredmaximumpacketlatenciesforfourdistributedBackoprotocolswithvaryinginjectionrates.Aswecanseethatcountingprotocolisso fasteroneamongthemandstillBinaryExponentialBackoistheslowestonewhile QuadraticBackofandCountingBackoareinbetweenthenQueueBackoisthe winnerinthisrespect.Asmentionedbeforewhentheinjectionrateislarge,thethe packetlatencyforBinaryExponentialBackoalgorithmistoolarge. 29
PAGE 38
5.1.3VaryingBurstiness Weconsideranotherscenarioofvaryingburstinesswithxednumberofstations, roundsandinjectionrate. Figure5.10:Threedeterministicalgorithms.ObservedvaluesmaximumpacketlatencyforvaryingBurstiness.Parametervalues: R =100 ; 000; n =10;injectionrate is1. Figure5.10considersasmallnumberofstations.ThenMBTFisbeatenwhile RRWiswinner.ThatmeansMBTFismoresensitivebynumberofstations,but RRWismoresensitivebyburstiness.SRRappearstocombinesensitivelytothe numberofstationsandburstiness. 30
PAGE 39
5.1.4VaryingNumbersofStations Thissectionisillustrateddierentnumberofstationswithxedburstiness, roundsandinjectionrate=0.75togureoutthemaximumpacketlatencyforsome deterministicandrandomizedalgorithms. Figure5.11:Observedvaluesmaximumpacketlatencyforvaryingnumberofstations. Parametervalues: R =100 ; 000; b =20;injectionrate=0 : 75. Figure5.11demonstratedhowMBTFisbeatenbecausethisprotocolismore eectivewithnumberofstationswhileRRWaectsbynumberofstations,burstiness andinjectionrate.WecanseethatSRRherebecomesthewinnerbecauseIxed numberofburstiness,rounds,andinjections.Itismoresensitivebyhowmany packetsthatinjectedineachstations;alsoitiseectivebynumberofstations,but moresensitivewithinjectionrateandmaximumpacketsthatcouldinjectperround. 31
PAGE 40
Figure5.12:Observedvaluesmaximumpacketlatencyforvaryingnumberofstations. Parametervalues: R =100 ; 000; b =20;injectionrate=0 : 75. Therandomizedprotocolsarealsoeectivebydierentnumberofstationsas wecanseeintheFigure5.12withabovesettingssetupthatmaximumlatencyfor BinaryExponentialBackOandQuadraticExponentialBackOalgorithmsareincreasedhighconcurrentlythenumberofstationsareincreased,but,ingeneralthe deterministicprotocolsarewinnerinordertocomparethemwithrandomizedwhen appliedtothisscenario. 32
PAGE 41
5.2Throughput Inthissectionisfoundthenumberofpacketsthatareinjectedandnumber ofpacketsthataresent;itisanotherwaytochecktheperformanceofeachalgorithm.Thesettingsthatusedtogureoutthesenumbersare n =200; b =20 ;L = 100 ; 000; = = 0 : 3. Table5.2:Throughput Algorithm PacketsInjected =0.05 PacketsSent =0.05 PacketsInjected =0.995 PacketsSent =0.995 RRW501950139951995456 SRR10037501919903799518 MBTF10036501219903792648 OFRRW501850189951896085 OFSRR501945909961948666 BEB491549159676456668 QEB492849289721835396 Table5.2summarizestheoutcomesofexperimentswhichreecthoweachprotocol worksunderlowandhighinjectionrates.WecannoticethatalgorithmRoundRobinWithholdingandOldFirstRoundRobinWithholdingperformcomparatively well.Theeciencyisapproximatedabout99%forRRWandOFRRW.SearchRoundRobinandMoveBigToFronteciencyareabout50%becauseitsentabout halfpacketsthatareinjectedinbothhighandlowinjectionrate.Thethroughputof algorithmOldFirstRoundRobinWithholdingisabout98%whentheinjectionrate islowwhilethethroughputisabout51%whentheinjectionrateishigh.Finally,the randomizedprotocolsaredoingperfectthroughputwhensetlowinjectionratewhere 33
PAGE 42
theeciencyforthemis100%;ontheotherhand,whenweappliedhighinjection ratealgorithmBinaryExponentialBackOthroughputisapproximately58%while algorithmQuadraticExponentialBackOisabout36%. 5.3FutureWork Weconsidered = whengeneratingpacketsperroundbecause.Thisisonly oneofpossibleapproachestocreateasimulationenvironmentrelatedtoworstcase adversarialmodels. Forfutureworktoimprovethisprojectortogetdierentoutcomesbyassuming isainjectionrateand isclosedto1thenseewhatwillgetfromthesechanges. Anotherwaytogeneratepacketseachroundassumesthat isverycloseto ,but itismorethan .Itassumesthatbecauseweneedtokeepbucketnonemptyand nonfulllikesomethinginbetweentoguaranteethatthesimulationcouldinjection numberofpacketseachroundwithoutidleorbusy.Inaddition,itconsideredthatthe randomizedadversarialinjectionsmodelcanactivateatmostonestationperround. Thereisanotherwaywecouldmodifythisapproachthatthemodelofadversary couldactivatemorethanonestationperround.Thischangeshouldgiveusdierent resultsbymeasuringpacketlatencyorotherfactors.Furthermore,itcanconsider otherdeterministicanddistributedprotocolsandsimulatethemandcomparetheir outcomes.Thistypeofstudyacceptsmanyassumptionsandsuggestionstogenerate packetsorthewaythattheadversarialinjectionmodelsimulatesortechniquesto activatestation 34
PAGE 43
CHAPTER VI CONCLUSION We proposed an adversarial model, called randomized leaky bucket adversar y that is amenable to simulations. It is determined by three parameters: injection rate, burstiness, and a parameter of a Poisson distribution. In simulations, it was always a 1activating static adversar y which means at most one station was activate per round. We simulated fve distributed deterministic protocols RoundRobinWithholding ( R RW ), OlderFirstRoundRobinWithholding ( OFR RW ), SearchRoundRobin ( SRR ), OlderFirstSearchRoundRobin ( OFSRR ), and MoveBigToFront ( MBTF ). The maximum packet latency and average latency was compared with the upper bounds (worstcase) for each algorithm. This allows to see the behavior of each algorithm when the parameters of the environment var y like injection rates or the numbers of stations. The simulations included two randomized algorithms Bina ryExponentialBackoff ( BEB ) and Quadr aticBackoff ( QB ). The backo protocols are considered in their windowed versions. They operate under the principle that a station tries to transmit the packets in the order of their injection, and when a new packet is available then the node selects a round uniformly at random in the current window and then waits for this round to occur and transmits the packet. The goal was to investigate by simulating these protocol is to compare them with fve deterministic protocols mentioned above. The result that got are rerecting the behavior of each algorithm. When the number of stations is a big as 200 and the burstiness gets fxed, with 19 incremented injection rates, MBTF is the beaten one while SRR is the winner among them because MBTF protocol is more sensitive with number of stations. We carried out a comparative study among randomized and deterministic algo35
PAGE 44
rithmstoseewhichisfasterandwhichisslowerbyusingsamesettingsforallof themandmeasuringthemaximumpacketlatencyforeach.Weobservedthatwhen theset10stationsandxedtheburstinesswith19varyinginjectionrates,BEBis thebeatenandSRRisthewinner.HereMTTFbecomesthewinnercomparedwith otherdeterministicprotocolbecauseofthesmallnumberofstationswecansaythat abigobservation. Furthermore,weconsideredthemaximumlatencyforrandomizedanddeterministicprotocolsfordierentnumbersofstationsandxedtheinjectionratetobe0.75 andburstinesstobe20.ItturnedoutthatCountingBackperformedworstamongall considereddeterministicalgorithmswhentheinjectionrateincreased.Forrandomizedprotocols,theyarealsosensitivewithnumberofstationswherethemaximumlatencyforalgorithm BinaryExponentialBackoff BEB increasedhigherthan themaximumpacketlatencyforalgorithm QuadraticBackoff QB .Indeed, withdierentnumberofstationtheBEBistheslowerprotocolamongallalgorithms thatareconsideredinthisprojectwhilealgorithmSearchRoundRobinisthefaster oneamongthem. 36
PAGE 45
REFERENCES [1]LakshmiAnantharamuandBogdanS.Chlebus.Broadcastinginadhocmultiple accesschannels. TheoreticalComputerScience ,584:155{176,2015. [2]LakshmiAnantharamu,BogdanS.Chlebus,DariuszR.Kowalski,andMariuszA.Rokicki.Deterministicbroadcastonmultipleaccesschannels.In Proceedingsofthe 29thIEEEInternationalConferenceonComputerCommunications (INFOCOM),pages1{5,2010. [3]LakshmiAnantharamu,BogdanS.Chlebus,DariuszR.Kowalski,andMariuszA.Rokicki.Mediumaccesscontrolforadversarialchannelswithjamming. In Proceedingsofthe 18thInternationalColloquiumonStructuralInformation andCommunicationComplexity(SIROCCO),volume6796of LectureNotesin ComputerScience,pages89{100.Springer,2011. [4]LakshmiAnantharamu,BogdanS.Chlebus,DariuszR.Kowalski,andMariuszA.Rokicki.Packetlatencyofdeterministicbroadcastinginadversarial multipleaccesschannels. CoRR ,abs/1701.00186,2017. [5]MatthewAndrews,BaruchAwerbuch,AntonioFernandez,FrankThomson Leighton,ZhiyongLiu,andJonM.Kleinberg.Universalstabilityresultsand performanceboundsforgreedycontentionresolutionprotocols. Journalofthe ACM ,48(1):39{69,2001. [6]MatthewAndrewsandLisaZhang.Routingandschedulinginmultihopwireless networkswithtimevaryingchannels.In ProceedingsoftheFifteenthAnnual ACMSIAMSymposiumonDiscreteAlgorithms(SODA) ,pages1031{1040,2004. [7]MichaelA.Bender,MartinFarachColton,SimaiHe,BradleyC.Kuszmaul,and CharlesE.Leiserson.Adversarialcontentionresolutionforsimplechannels.In Proceedingsofthe 17thACMSymposiumonParallelAlgorithmsandArchitectures(SPAA),pages325{332,2005. [8]DanielS.Berger,MartinKarsten,andJensSchmitt.Ontherelevanceof adversarialqueueingtheoryinpractice. SIGMETRICSPerform.Eval.Rev. 42(1):343{354,June2014. [9]AllanBorodin,JonKleinberg,PrabhakarRaghavan,MadhuSudan,andDavidP. Williamson.Adversarialqueuingtheory. JournaloftheACM ,48(1):13{38,January2001. 37
PAGE 46
[10]BogdanS.Chlebus.Randomizedcommunicationinradionetworks.InPanosM. Pardalos,SanguthevarRajasekaran,JohnH.Reif,andJoseD.P.Rolim,editors, HandbookofRandomizedComputing ,volumeI,pages401{456.KluwerAcademic Publishers,2001. [11]BogdanS.Chlebus,DariuszR.Kowalski,andMariuszA.Rokicki.Maximum throughputofmultipleaccesschannelsinadversarialenvironments. Distributed Computing,22(2):93{116,2009. [12]BogdanS.Chlebus,DariuszR.Kowalski,andMariuszA.Rokicki.Adversarialqueuingonthemultipleaccesschannel. ACMTransactionsonAlgorithms 8(1):5:1{5:31,2012. [13]RobertG.Gallager.Aperspectiveonmultiaccesschannels. IEEETransactions onInformationTheory ,31(2):124{142,1985. [14]LeslieAnnGoldberg,MarkJerrum,SampathKannan,andMikePaterson.A boundonthecapacityofbackoandacknowledgmentbasedprotocols. SIAM JournalonComputing,33(2):313{331,2004. [15]JohanHastad,FrankThompsonLeighton,andBrianRogo.Analysisofbacko protocolsformultipleaccesschannels. SIAMJournalonComputing ,25(4):740{ 774,1996. [16]RobertM.MetcalfeandDavidR.Boggs.Ethernet:Distributedpacketswitching forlocalcomputernetworks. CommunicationsoftheACM ,19(7):395{404,1976. [17]MichaelMitzenmacherandEliUpfal. ProbabilityandComputing.Cambridge UniversityPress,Secondedition,2017. [18]PrabhakarRaghavanandEliUpfal.Stochasticcontentionresolutionwithshort delays. SIAMJournalonComputing,28(2):709{719,1998. [19]SheldonM.Ross. Simulation.Elsevier,Fifthedition,2013. 38

