The disclosed method may include (1) establishing a communication session between a plurality of network nodes to enable the plurality of network nodes to exchange route updates with one another, and then during the communication session, (2) detecting, at one of the network nodes, at least one route update to send to another one of the network nodes, (3) compressing, at the network node, the route update to reduce an amount of data included in the route update, and then upon compressing the route update, (4) sending the compressed route update to the other network node to enable the other network node to forward traffic along a path whose route is advertised in the compressed route update. Various other methods, systems, and apparatuses are also disclosed.