Patent ID: 8792506

Claim:
An apparatus, comprising: a receiving mechanism configured to receive a first packet that is to be routed from a first node in a first Autonomous System (AS) to a second node in a second AS; a determining mechanism configured to determine a set of bits that encodes a route in an n-ary tree that includes the first node and a root node in the first AS, wherein each node in the route corresponds to a subset of the set of bits that identifies an outgoing edge of the node over which the first packet is to be routed; a generating mechanism configured to generate, based on the first packet, a second packet that includes the set of bits and an identifier associated with the second AS, wherein the second packet is an Ethernet packet, and wherein the set of bits are stored in one or more VLAN (Virtual Local Area Network) tags; and a sending mechanism configured to send the second packet to the root node in the first AS.