DescriptionQ1061
Q1061ArchBroadcomASIC interview problem
IPv4 longest-prefix-match model
TechniquesArchMicroarchitectureInterconnectIPv4model
DifficultyHard
TopicComputer Architecture
LanguageC++
Requirements4 checkpoints
01
Problem
A switch reference model searches up to 64 IPv4 route entries. Write a C++ longest-prefix-match function with fixed error and tie rules.
Starting declarationC++
struct route { uint32_t prefix; uint8_t length, port; };
int lpm(const route *r, size_t n, uint32_t addr,
uint8_t *port, size_t *index);Example input and output
Use this case to check your interpretationInput
Routes are 10.0.0.0/8 to port1 and 10.1.0.0/16 to port2; address is 10.1.2.3.Output
lpm returns 1, port=2, and index identifies the /16 entry.Explanation
Both prefixes match, but the sixteen-bit prefix is longer and therefore wins.
02
Requirements (4)
- Require port and index, allow r=null only when n=0, require n<=64, and require every length<=32; return -1 and preserve outputs on an error.
- An entry matches when the top length bits of addr and prefix agree; length zero is the default route and performs no shift by 32.
- Choose the matching entry with the greatest length; if identical lengths tie, choose the lower array index.
- Return 1 and write port/index on a match; return 0 and preserve both outputs when no entry matches.