A traffic flow based map cache refresh may be provided. A computing device may receive a dropped packet message when a packet associated with a flow having a destination and a source was dropped before it reached the destination. Next, in response to receiving the dropped packet message, a map request message may be sent to a Map Server (MS). In response to sending the map request message, a map response message may be received indicating an updated destination for the flow. A map cache may then be refreshed for the source of the flow based on the updated destination from the received map response message.