1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ268

Page ↗

Q268ArchDVASIC interview problem

Token-Bucket Rate-Limit Monitor

TechniquesDVArchRate limitingSaturating arithmeticStatistics

DifficultyMedium

TopicPerformance Control

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Model a token-bucket limiter and verify whether each packet should be accepted or throttled. Tokens accumulate while idle but never exceed the configured burst capacity.

Class declarationSystemVerilog

class TokenBucket;
  function new(int capacity, int refill_tokens, int refill_period);
  void tick();
  bit accept(int cost);
  int available_tokens();
endclass

Example input and output

Use this case to check your interpretation

Input

capacity=4, refill=1 token/cycle
cycle 0 request cost=3
cycle 1 request cost=2
cycle 2 request cost=2

Output

cycle 0 allow (tokens 1)
cycle 1 allow after refill (tokens 0)
cycle 2 deny after refill (tokens 1)

Explanation

Tokens saturate at capacity, refill before admission, and are consumed only by allowed requests.

Requirements (4)

Refill at the configured rate and saturate exactly at capacity.
A packet is accepted only when its complete cost can be consumed without underflow.
Define deterministic ordering when refill and consume occur in the same cycle.
Reject invalid configuration and nonpositive packet cost.