How can I get Windows to see Linux host names and vice versa?

I have Windows and Linux machines on the same subnet. My router configuration correctly tells me both their machine names, and their IP addresses. However, when I try and ping a Linux machine from a Windows machine, or ping a Windows machine from a Linux machine, I need to use IP addresses rather than names. If I'm pinging a Windows machine from a Windows machine, or a Linux machine from a Linux machine, the machine name correctly resolves without any hosts file entries.

Why is this?

I would have thought my router (D-Link DIR-655) would act as a DNS server itself. I see it has an option called "Enable DNS Relay", but from what I've read this won't help me. If it's relevant, the DIR-655 is used for internal traffic, with my ISP's Netgear DGN1000 used as a gateway to the Internet. It's on a different subnet though, and all my machines connect to my DIR-655, not the DGN1000.

What do I need to do to have host names automatically resolved within my subnet regardless of the operating system that they're running?

You need a name resolution server of some sort.

First setup a DNS server that accepts dynamic updates on one machine that has a static IP. BIND is the obvious choice (installs on Windows and Linux) but there are other Linux versions that work just as well such as DJBDNS etc... Your DNS server will need to forward requests to your ISP's DNS server or to some other public DNS server. A good domain name that should be safe enough to use is "home.internal" No need to register it and it is not a public domain... This machine you set DNS onto will need to be up all the time...

Once that is setup, tell your reouter's DHCP server to hand out the IP of the DNS server you just setup.

ARP host names are different from NetBIOS names.

Windows bases itself on NetBIOS names where as Linux bases itself on the host names.

Your router receives the host names through ARP / DHCP; yes, Windows does have host names too.

You need to have your router host the hostnames in it's DNS or you'll need to adjust all the hosts file.

If your router doesn't support it, you could look into installing DD-WRT on your router and using dnsmasq together with a hosts file where you will fill in the hosts. I would deem that's pretty much a work-around though, do you really want to do this just to be able to ping? Not a daily computer activity...

I know your pain, it's completely insane that in 2011, host names don't just "work", right out of the box.

Another option is Bonjour. It's an Apple technology, but there are implementations for Linux (Avahi) and Windows (Bonjour for Windows). Bonjour let's you access other computers using the syntax:

<hostname>.local

I went with this solution, because I don't have a DD-WRT compatible router, or an always-on server to run DNS. Also, once its set up, you don't have to worry about whether an IP changes, like with a hosts file.