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

DescriptionQ266

Page ↗

Q266FWArchASIC interview problem

Longest-Prefix-Match Routing Table

TechniquesFWArchDVTrieIPv4Prefix matching

DifficultyHard

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Implement an IPv4 routing table that returns the next hop associated with the longest prefix matching a 32-bit destination address.

Class declarationSystemVerilog

class RouteTable;
  bit insert(bit [31:0] prefix, int prefix_len, int next_hop);
  bit remove(bit [31:0] prefix, int prefix_len);
  bit lookup(bit [31:0] addr, output int next_hop);
endclass

Example input and output

Use this case to check your interpretation

Input

routes: 10.0.0.0/8 -> A, 10.1.0.0/16 -> B
lookup: 10.1.2.3

Output

next_hop = B

Explanation

Both prefixes match, but /16 is longer and therefore wins over the broader /8 route.

Requirements (4)

Support prefix lengths from /0 through /32.
A repeated insert updates the existing route rather than creating a duplicate.
Lookup must select the most-specific match and report failure if none exists.
Normalize or reject prefixes whose host bits are nonzero.