Techniques for maintaining an always-on data session for an access terminal are described. Messages to keep alive the data session may be sent using non-traffic channels to avoid bringing up traffic channels just to send these messages. In one design, an access network may send a first message (e.g., a RouteUpdateRequest message) on a first non-traffic channel (e.g., a control channel) to the access terminal. The access terminal may return a second message (e.g., a RouteUpdate message) on a second non-traffic channel (e.g., an access channel) to the access network. The access network may then send a third message (e.g., for an Echo-Request) on the first non-traffic channel over a smaller area covering an approximate location of the access terminal, which may be determined based on the second message. The access terminal may return a fourth message (e.g., for an Echo-Reply) on the second non-traffic channel to the access network.