Methods and apparatus providing two stage tunneling

A system for routing packets, the system comprising:

• a first computerized device;
• and
• a second computerized device;
• wherein the first computerized device is configured to perform the operations of:
• receiving a packet from a first node in a first autonomous system (AS), the packet addressed to a second node in a second AS;
• identifying the second computerized device from among a plurality of network devices without identifying, at the first computerized device, a route to the second node from the second computerized device, the network devices being within the first AS, the second computerized device including routing information received over a border gateway protocol (BGP) for each of at least one node in the second AS, the plurality of network devices comprising a subset of partial routing nodes and a subset of full routing nodes, the first computerized device and the subset of partial routing nodes failing to include the routing information received over the BGP for each of the at least one node in the second AS, each of the subset of full routing nodes including the routing information received over the BGP for each of the at least one node in the second AS, and the subset of full routing nodes including the second computerized device;
• transmitting the packet from the first computerized device to the second computerized device over a first tunnel without identifying the route to the second node from the second computerized device, wherein transmitting the packet to the second computerized device is based on identification of the second computerized device as including the routing information received over the BGP for each of the at least one node in the second AS;
• and
• wherein the second computerized device is configured to perform the operations of:
• receiving the packet from the first computerized device over the first tunnel;
• establishing a second tunnel on the route to the second node from the second computerized device;
• and
• transmitting the packet to the second node over the second tunnel.

A computerized device comprising:

• a memory;
• a processor;
• a communications interface;
• an interconnection mechanism coupling the memory, the processor and the communications interface;
• wherein the memory is encoded with a packet routing application that, when executed on the processor, performs the operations of:
• receiving a packet via the communications interface, the computerized device being a first node in an autonomous system (AS), the packet destined for a second node in the AS;
• indentifying, 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 in the AS, the plurality of nodes in the AS including the plurality of network devices, 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 failing to include the BGP routing information for each of the plurality of nodes, the subset of full routing nodes including the BGP routing information for each of the plurality of the nodes, wherein the subset of full routing nodes includes the full routing node;
• and
• transmitting the packet from the first node to the full routing node over a first tunnel established without knowledge of how to route the packet from the full routing node to the second node, wherein transmitting the packet is based on the full routing node being identified as including the BGP routing information for each of the plurality of nodes, and wherein the full routing node establishes a second tunnel from the full routing node to the second node.

A non-transitory tangible computer readable storage medium encoded with computer programming instructions that, when executed by a processor in a computerized device, provides packet routing, the non-transitory tangible computer readable storage medium comprising:

• instructions to receive a packet at a first node in an autonomous system (AS), the packet destined for a second node;
• instructions to identify, 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 in 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 in the AS, wherein each node in the subset of full routing nodes is configured to include the BGP routing information for each of the nodes in the AS, wherein the subset of full routing nodes includes the full routing node;
• and
• instructions to transmit the packet from the first node to the full routing node over a first tunnel, without knowledge of a route to the second node from the full routing node, wherein the full routing node transmits the packet over a second tunnel from the full routing node to the second node.