spacer
       
Home
About the Department
Programs & Admissions
Curricula & Courses
Research
Faculty & Staff
Seminars
Physics Intranet
Announcements
Community Outreach
Contact
Links
Visitors Counter
2546639  
Home arrow Research arrow Research areas and activities arrow Information physics arrow Play with the Leaky Bucket animation game

Play with the Leaky Bucket animation game

Click here to start the game

[1] You can use the tap to control the entrance of water drops into the leaky bucket.
[2] If your tap is too loose, water will overflow. If 20 drops of water overflow, the game is over. See how many drops of water you can collect before the game stops.
[3] You can play on forever if your tap is tight enough, but then your water level in the bucket will not be high enough. See how high you can maintain the average water level, while you aim at restricting the overflow ratio to 1% or below.
[4] You can change to the automatic mode, in which the tap is controlled by an SDCA algorithm (see below).

Stochastic Processes

Water drops enter the leaky bucket stochastically. They also leak out at the bottom stochastically. Hence the movement of the water level is a stochastic process described by a diffusion equation. The process is similar to the diffusion of a drop of ink in water.

However, there is an important difference between the water level movement and ink diffusion. When the capacity of the bucket is filled, there will be an overflow. This modifies the diffusion process, as illustrated in the figure below for buckets with capacities of 20 channels (filled symbol) and 10 channels (open symbol) respectively. (1 channel = 1 drop of water). To control the overflow rate, we need to know the solution of the diffusion equation for a bucket with a finite capacity.

Applications

Knowing how the water level changes with time, we can control the water level. This method can be used in the control of wireless mobile networks, if we recognize the following analogy:

Leaky bucket

Wireless mobile networks

Bucket size

Channel capacity of a base station

Water drops from the tap

New calls

Water drops leaking from the bottom

Completed calls

Water drops prevented from entering the bucket by the tap

Blocked calls (terminated before the phone starts)

(To be added in the next version of the game.) Water from an extra pipe

Hand over calls (mobile calls switching from a neighboring base station)

Water drops overflowing

Dropped calls (terminated in the middle of a phone conversation, very annoying*)

The task: to maintain a high water level in the bucket, while restricting the overflow rate to 1% or below

The task: to maintain a high level of channel utilization in the base station, while restricting the dropping probability to 1% or below

* Remark: In real networks, the dropped calls are not the new calls, but the hand over calls. This analogy will be included in the next version of the game.

Reference

The control method is used in the Stable Dynamic Call Admission Control (SDCA) algorithm. Details can be found in the following paper:

S. Wu, K. Y. Michael Wong and B. Li, ˇ°A Dynamic Call Admission Policy with Precision QoS Guarantee Using Stochastic Control for Mobile Wireless Networksˇ±, IEEE/ACM Trans. on Networking 10, 257-271 (2002).
 

spacer
Copyright © 2007 Department of Physics, HKUST. All rights reserved.