What are the networking requirements for a successful AirPlay connection? We are using devices we know are capable of AirPlay (iphone 5 on ios7, apple tv3). Sometimes the phone can see the apple tv, sometimes it cannot. When it cannot, we check, and the apple tv IS still on. What must be true for the phone to see the apple tv?

Of course they must be on the same wireless network. this is true. However our network is large (we are not in a home), and so there must be some other issues. We even checked and both the phone and apple tv are on the same subnet. What else must be true? must certain ports be open, etc, etc.?
Per Apple KB article HT6175, AirPlay makes use of a number of ports:


╔══════╦═════════╦════════════════════════════════════════╗
║ Port ║ TCP/UDP ║                  Name                  ║
╠══════╬═════════╬════════════════════════════════════════╣
║   80 ║ TCP     ║ Hypertext Transfer Protocol (HTTP)     ║
║  443 ║ TCP     ║ Secure Sockets Layer (SSL, or "HTTPS") ║
║  554 ║ TCP/UDP ║ Real Time Streaming Protocol (RTSP)    ║
║ 3689 ║ TCP     ║ Digital Audio Access Protocol (DAAP)   ║
║ 5353 ║ TCP     ║ Multicast DNS (MDNS)                   ║
╚══════╩═════════╩════════════════════════════════════════╝