Identifying an egress point to a network location

• US 9,143,429 B2
• Filed: 02/28/2012
• Issued: 09/22/2015
• Est. Priority Date: 02/28/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Padgett, Steven
• Primary Examiner(s): Mattis, Jason
• Assistant Examiner(s): Baig, Adnan
• Application Number:
  US13/407,066
• Publication Number:
  US 20130223276A1
• Time in Patent Office: 1,302 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A method of identifying an egress point to a network location includes receiving a client connection from an external network (e.g., the internet) and retrieving an egress point identifier from an egress data source (e.g., a database, look-up table, hash table, data object etc.) for the received client connection. The egress data source stores egress point identifiers associated with at least one of an internet protocol address and a subnetwork. The method further includes binding the client connection to an egress point corresponding to the retrieved egress point identifier, encapsulating packets of data received from the client connection, and sending the encapsulated data packets through an instantiated network tunnel to the bound egress point. The method includes decapsulating the encapsulated data packets at least near the bound egress point. A default routing policy may then guide the data packets to the egress point.

Claims

1. A method of identifying an egress point to a network location, the method comprising:

receiving a client connection containing packets of data from an external network;

retrieving an egress point identifier from an egress data source for the received client connection, the egress data source storing egress point identifiers associated with at least one of an internet protocol address and a subnetwork;

binding the client connection to a pre-selected egress point corresponding to the retrieved egress point identifier, the pre-selected egress point different from another egress point naturally selected by a default network routing protocol;

encapsulating the packets of data received from the client connection;

instantiating a network tunnel to an intermediate egress point located a threshold distance from the bound pre-selected egress point;

sending the encapsulated data packets through the instantiated network tunnel to the intermediate egress point;

decapsulating the encapsulated data packets at the intermediate egress point; and

after decapsulating the encapsulated data packets, routing the decapsulated packets from the intermediate egress point to the bound pre-selected egress point using the default network routing protocol.

2. The method of claim 1, further comprising instantiating network tunnels of a provider network for each pre-selected egress point having a corresponding egress point identifier stored by the egress data source.

3. The method of claim 2, further comprising:

receiving an advertised tunnel endpoint from a decapsulator associated with each pre-selected egress point; and

for each received tunnel endpoint advertisement, instantiating a network tunnel to the associated pre-selected egress point.

4. The method of claim 1, further comprising:

receiving an advertised tunnel endpoint from a decapsulator associated with each pre-selected egress point; and

for each received tunnel endpoint advertisement, configuring the associated decapsulator to terminate encapsulated data packets received through a network tunnel.

5. The method of claim 1, further comprising querying the egress data source for an egress point identifier associated with a destination of the received client connection, the destination comprising at least one of an internet protocol address and a subnetwork.

6. The method of claim 1, further comprising querying the egress data source for an egress point identifier corresponding to a pre-selected egress point satisfying a performance criteria.

7. The method of claim 6, wherein the performance criteria comprises at least one of a threshold latency, a threshold bandwidth, a threshold cost, and a threshold usage.

8. The method of claim 1, further comprising encapsulating the data packets with received tunnel label information.

9. The method of claim 8, wherein the tunnel label information comprises at least one of a network tunnel identifier, a tunnel type, and an egress point identifier.

10. The method of claim 1, further comprising sending the data packets received from the client connection according to a default network routing protocol when the egress data source fails to provide an egress point identifier for the received client connection.

11. A network system comprising:

an egress data source storing egress point identifiers associated with at least one of an internet protocol address and a subnetwork;

a tunnel manager instantiating network tunnels of a provider network for each pre-selected egress point having a corresponding egress point identifier stored by the egress data source;

a connection manager in communication with the egress data source and the tunnel manager, the connection manager;

receiving a client connection containing packets of data from an external network;

retrieving an egress point identifier from the egress data source for the received client connection;

binding the client connection to a pre-selected egress point corresponding to the retrieved egress point identifier, the pre-selected egress point different from another egress point naturally selected by a default network routing protocol;

encapsulating the packets of data received from the client connection;

instantiating a network tunnel to an intermediate egress point located a threshold distance from the bound pre-selected egress point; and

sending the encapsulated data packets through an instantiated network tunnel to the intermediate egress point; and

a decapsulator decapsulating the encapsulated data packets at the intermediate egress point;

wherein after decapsulating the encapsulated data packets at the decapsulator, the connection manager routes the decapsulated data packets from the decapsulator to the bound pre-selected egress point using the default network routing protocol.

12. The network system of claim 11, wherein the tunnel manager:

receives a tunnel end point advertisement from a decapsulator associated with each selected egress point; and

for each received tunnel endpoint advertisement, instantiates a network tunnel to the associated pre-selected egress point.

13. The network system of claim 11, wherein the tunnel manager:

receives a tunnel end point advertisement from a decapsulator associated with each pre-selected egress point; and

for each received tunnel endpoint advertisement, configures the associated decapsulator to terminate encapsulated data packets received through a network tunnel.

14. The network system of claim 11, wherein the tunnel manager provides tunnel label information to the connection manager, the connection manager encapsulating the data packets with the tunnel label information.

15. The network system of claim 14, wherein the tunnel label information comprises at least one of a network tunnel identifier, a tunnel type, and an egress point identifier.

16. The network system of claim 11, wherein the egress data source stores at least one performance factor for association with at least one pre-selected egress point.

17. The network system of claim 16, wherein the performance factor comprises at least one of latency, bandwidth, cost, and usage.

18. The network system of claim 11, wherein the connection manager sends the data packets received from the client connection according to a default network routing protocol when the egress data source fails to provide an egress point identifier for the received client connection.

19. The network system of claim 11, wherein the pre-selected egress point comprises an egress router.

20. A computer program product encoded on a non-transitory computer readable storage medium comprising instructions that when executed by a data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving a client connection containing packets of data from an external network;

retrieving an egress point identifier from an egress data source for the received client connection, the egress data source storing egress point identifiers associated with at least one of an internet protocol address and a subnetwork;

binding the client connection to a pre-selected egress point corresponding to the retrieved egress point identifier, the pre-selected egress point different from another egress point naturally selected by a default network routing protocol;

encapsulating the packets of data received from the client connection;

instantiating a network tunnel to an intermediate egress point located a threshold distance from the bound pre-selected egress point;

sending the encapsulated data packets through the instantiated network tunnel to the intermediate egress point;

decapsulating the encapsulated data packets at the intermediate egress point; and

after decapsulating the encapsulated data packets, routing the decapsulated packets from the intermediate egress point to the bound pre-selected egress point using the default network routing protocol.

21. The computer program product of claim 20, wherein the performed operations further comprise instantiating network tunnels of a provider network for each selected egress point having a corresponding egress point identifier stored by the egress data source.

22. The computer program product of claim 20, wherein the performed operations further comprise:

receiving an advertised tunnel endpoint from a decapsulator associated with each selected egress point; and

for each received tunnel endpoint advertisement, instantiating a network tunnel to the associated pre-selected egress point.

23. The computer program product of claim 20, wherein the performed operations further comprise:

receiving an advertised tunnel endpoint from a decapsulator associated with each pre-selected egress point; and

for each received tunnel endpoint advertisement, configuring the associated decapsulator to terminate encapsulated data packets received through a network tunnel.

24. The computer program product of claim 20, wherein the performed operations further comprise querying the egress data source for an egress point identifier associated with a destination of the received client connection, the destination comprising at least one of an internet protocol address and a subnetwork.

25. The computer program product of claim 20, wherein the performed operations further comprise querying the egress data source for an egress point identifier corresponding to a pre-selected egress point satisfying a performance criteria.

26. The computer program product of claim 25, wherein the performance criteria comprises at least one of a threshold latency, a threshold bandwidth, a threshold cost, and a threshold usage.

27. The computer program product of claim 20, wherein the performed operations further comprise encapsulating the data packets with received tunnel label information.

28. The computer program product of claim 27, wherein the tunnel label information comprises at least one of a network tunnel identifier, a tunnel type, and an egress point identifier.

29. The computer program product of claim 20, wherein the performed operations further comprise sending the data packets received from the client connection according to a default network routing protocol when the egress data source fails to provide an egress point identifier for the received client connection.