Patent ID: 8077721

Claim:
A method of routing packets, the method comprising: receiving a packet at a first node in an autonomous system (AS), the packet destined for a second node in the AS; identifying, at the first node, a full routing node from among a plurality of network devices in the AS based on the full routing node including Border Gateway Protocol (BGP) routing information for each of a plurality of nodes within the AS, the plurality of network devices comprising a subset of partial routing nodes and a subset of full routing nodes, the first node and the subset of partial routing nodes not including the BGP routing information for each of the nodes within the AS, the subset of full routing nodes including the BGP routing information for each of the nodes within the AS, the subset of full routing nodes including the full routing node, wherein the nodes within the AS include the network devices; transmitting the packet from the first node over a first tunnel to the full routing node based on identification of the full routing node as including the BGP routing information for each of the nodes in the AS; and routing the packet at the full routing node to the second node over a second tunnel.