Incremental Solution - 2 [Under Telecom > Base station scheduling]
If we put HPVR allocation requests ahead of CR queue, it may create trouble as HPVR is likely eat up allocation which is to go for CR. This can be avoided if we keep certain buckets reserved for HPVR traffic. These reserved buckets are to go unallocated if there is no HPVR traffic. In practice, HPVR traffic mean system specific and shared data, so there will always be HPVR traffic. Anyway how do we keep certain buckets reserved fog HPVR ? We can do that by having service level allocation criterion for HPVR service queue. If this criterion is matched, Scheduler Engine is to traverse through HPVR allocation requests just like it would do for other service queues. The difference is if the bucket remains unallocated after traversinig through HPVR service queue, Scheduler Engine is to keep it unallocated and not go for next service queue.
The next question would be: can we make numbers of buckets that are reserved for HPVR traffic dynamic ? That is can we have certain static reservation for HPVR and increase it in case there is need ? Yes, we can do that by updating top level allocation criteria and before doing it making sure that it would not conflict with any of the existing CR allocations !
Let us now extend earlier example with inclusion of System user and User4 requiring HPVR allocation of one bucket of data each. Also, say the static configuration for HPVR traffic is "every 24th and 25th bucket". Our HPVR allocation criterion would of course be "every 24th and 25th bucket".
Allocator would queue up two allocations requests { System user require any one bucket } and { User4 require any one bucket } in HPVR queue. Resulting allocation queue would look like as below:
| Bucket # | User |
| n | System User |
| n+1 | User4 |
| n+2 | User1 |
| n+3 | User2 (R3) |
| n+4 | User3 (R7) |
| n+5 | User2 (R2) |
| n+6 | User3 (R6) |
| n+7 | User2 (R1) |
| n+8 | User3 (R5) |
| n+9 | User1 |
| n+10 | User2 (E) |
| n+11 | User3 (R4) |
| n+12 | User3 (R3) |
| n+13 | User3 (R2) |
| n+14 | User3 (R1) |
| n+15 | User3 (E) |
| n+16 | User1 |
| n+17 | - |
For fairness, we need to have circular and moving queue for HPVR allocation requests like the one for VR (as discussed in earlier article).
Till now we assumed no particular values for minimum and maximum data rate for VR requests. Let us now try if we can take care of service requirements if there are certain values for minimum and maximum data rate values present for VR requests.
We need to attach "history" to each allocation request in VR queue that would help us in calculating actual resulting data rates for VR requests. Note that when we talk about data rates for VR traffic, it is average data rate calculated over certain period of time Th (» Δt). So history should pertain to last T h period and should be updated after every Δt for all VR allocation requests. To achieve fairness, we made the VR queue circular and advanced pointer after every allocation. Now in this case, to achieve service requirements related to min/max data rates, we need shuffle the queue based on history calculations made after every Δt (or after every VR allocation). The allocation request for which the history calculated rate is close to minimum rate should come ahead in queue. The more closer it is to its minimum rate, more ahead it should be in VR service queue !
Here is updated diagram of data structures after discussed solutions.
Till now we did not worry much about allocator functions; we only mentioned how it converts original allocation request into internal per bucket allocation requests. But while it does the conversion and puts it into appropriate queue, it must do a very important function; the function to decide whether there is capacity in the system to take care of new allocation request. It is obvious that this is to be done based on service class of new allocation request. But here is one general way to find out if the new request can be taken care.
We can calculate available system capacity at every Δt time in terms of average data rate in last Th period and then when new request comes, we can decide quickly if the new request can be taken care without impacting service requirements of existing allocations.
The calculation of system capacity is not so difficult to make; here we can maintain history for available capacity and do history calculations every Δt (similar to what we decided to do for VR in our earlier discussion). If the current bucket remain unallocated after traversing VR queue, we take it into account in history calculations of available capacity.
I hope the reader now has fair idea about challenges involved in designing scheduler logic in base stations. I would continue to think of further possible traffic scenarios and try to look for better and better solutions. I would update the blog with the outcomes.
| Copyright © Samir Amberkar 2010-11 | § |
| Incremental solution - 1 « | Base Station Scheduling Index | . |