An ability to compress packets is announced from a customer edge router (CE) to other CEs through a routing protocol packet. An announcement of that ability is received from another CE through a routing protocol packet. A compression technique is then matched. The CE receives compression information from the other CE in a routing protocol packet, and determines that a compression technique identified therein matches any compression technique the CE is programmed to use. The CE then flags packets transmitted from/received by the CE to be compressed/decompressed according to the matched compression technique. Alternatively, the CE may match by transmitting compression information identifying a compression technique to the another CE in a routing protocol packet; the another CE receives the routing protocol packet and determines that a compression technique identified in the compression information of the routing protocol packet matches any compression technique the another CE is programmed to use.