An autonomous system includes at least some packet network devices that are capable of operating in a virtual route aggregation environment and some packet network devices that are not capable of operating in a virtual route aggregation environment. The autonomous system includes at least one egress border router, at least one aggregation router and at least one intermediate router. The egress border router uses an interior border gateway protocol to distribute a label message to the other routers in the autonomous system, the label message including a next hop MAC address associated with either an external router or the egress border router. The egress border router and the intermediate router using information included in the label message to contrast layer 2 table entries and the aggregation router using information included in the label message to construct a layer 3 table entry. The aggregation router receives a packet with a virtual prefix that corresponds to a virtual prefix in a list of virtual prefixes stored by the aggregation router, and routes the packet over a virtual path corresponding to one of the virtual prefixes.