Teredo is a service that enables hosts located behind one or more IPv4 NATs to obtain IPv6 connectivity by tunneling packets over IPv4 UDP. Under the national IPv6 deployment project in Taiwan, we developed the first Linux-based Teredo service in 2003. In this paper, we explain how IPv6 candidates located behind NATs can enlist the help of "Teredo servers" and "Teredo relays" to learn their "global addresses" and to obtain connectivity, and how clients, servers and relays can be organized in Teredo networks. We also describe in details our strategies for implementing Teredo server and Teredo relay under Linux, and show the performance of different Teredo implementations in public domain.