I have a bridge, over WiFi, that is using parprouted to fudge ARP so that routing works. Is there anything like dhcrelay (which relays DHCP requests) but for NetBIOS (Windows File and Print Sharing) names?
The WiFi gateway in question is a cheap Belkin so any other options seem unlikely to work.
UPDATE: I will use nmbd from samba as a WINS server. DHCP should allow me to configure WINS automatically on the client.
WINS and/or the later versions of DNS (which allow auto-registration - Bind 9 and up). Note: neither are NetBIOS, but replacement technologies for spanning/extending Windows resolutions across networks.
WINS alone will not be enough if you do not configure your clients to actually use the WINS server. There is a thing called WINS proxy which will forward NetBIOS broadcast name queries to a WINS server and re-broadcast its replies. Samba's nmbd implements it as well.
A poor man's solution is an IP helper configuration which has been implemented with some older routers - I think using an iptables DNAT for broadcast addresses should be able to mimic this functionality and work in a similar way.