Methods, systems, and apparatus are presented for performing network probing. A user equipment device (UE) may store a record associating traditional service set identifiers (SSIDs) with corresponding Short SSIDs. According to some embodiments, the UE may receive a message including a Short SSID, and determine whether a corresponding full SSID is known to the UE. Based on the determination, a probe request may be generated, addressed to either the Short SSID or the full SSID. After transmitting the probe request, the UE may receive a probe response, which may include a full SSID corresponding to the Short SSID. The UE may store a record associating the full SSID with the Short SSID, if applicable. According to some embodiments, a UE may receive a plurality of messages including respective SSIDs, and may generate a single probe request addressed to the SSIDs. The UE may receive a plurality of probe responses.