Summarize and paraphrase

Document Preview:

1. Consider a system of n stations attached to a multiple access channel and the leaky-bucket adversary with injection rate 1 and burstiness b + 1. The stations execute algorithm Move-Big-To-Front(n). Propose a strategy of the adversary to make the maximum number of packets queued by the stations in some round as large as possible. Give this maximum number of packets queued in the n stations together at some rounds of the execution when this strategy is applied. Answer1) The protocol is executed in a given round as follows. A station p with the token broadcasts a packet, if it has any. If the station with the token does not have a pending packet, then the station does not transmit, which results in a silent round. A station considers itself big in a round when it has at least n packets available. A big station attaches a control bit to indicate this status to each packet it transmits while big. After a station announces itself to be big, it is moved to the front of the list and keeps the token for the next round. After a station with token broadcasts while it is not big or when it does not transmit at all, then the token is moved immediately to the next station in the list. Here being “next” is understood in the cyclic ordering of the list of stations, in that the token from the last station in the list is moved directly to the first one. Theorem7. If protocol Move-Big-To-Front(n) is executed against a leakybucket adversary, then the number of packets stored in queues is O(n2). Define a pass of the token to be a traversal of the token starting at the front of the list and ending either at a new big station or again at the front station of the list after traversing the whole list, whichever occurs first. Define a life cycle of a station to be a time period which starts either in the first round of the execution or in a round when the station is discovered to be big, and which ends just before the station is discovered to be big again. Stability of protocol...