Homing pigeon
The variety of domesticated doves called homing pigeon have been selectively bred to be able to find their way home over extremely long distances. Since any pigeon will generally return to its own nest and its own mate, it was relatively easy to selectively breed the birds that found their ways home over repeated long flights. The birds carry messages (frequently written on cigarette paper) in small tubes that are attached to one of their legs. Flights at least as long as 1689 miles have been made by exceptional birds in competition. Their average flying speed over moderate distances is around 30 miles per hour, and they can achieve bursts of speed at around 40 miles per hours. For an informative magazine article written in the 1880s, see an on-line version at this external site.See this picture of a homing pigeon from the Pecos Valley Racing Pigeon Club. (Note the straight slope from the top of the head to the beak, and the prominent band around the nostrils.)
These birds should be distinguished from carrier pigeons, another breed entirely. That breed may originally have also been used to carry messages, but it is now a bird that departs more from the appearance of the original wild pigeons than do many of the other ornamental breeds and cannot fly very well.