Using a network overlay is one way to implement an SDN architecture. An overlay network is a computer or storage network built on top of another network and connected by virtual or logical links. In the context of software-defined networks (SDNs), an overlay network uses virtual links to connect to the underlying physical network (e.g., Ethernet switches or routers).
With SDN implementations, the software-defined network can either be built as the logical network (e.g., with a server) or, more commonly, as an overlay on an existing physical Ethernet network consisting of switch and routers.
Physical networks are extremely efficient at moving packets at high speed and high reliability. The challenge that SDN is trying to address, however, is the ability to make the physical network more Agile so it can respond quickly to changes in network requirements -- for example, the provisioning of new compute workloads and virtual machine mobility.
It is likely that initially, the majority of SDN implementations will use SDN to improve the flexibility and operations of an existing physical network -- which would make it an SDN overlay network. As the technology matures, organization may decide to implement "native" SDN protocols as their primary network.