Path selection system

• US 7,720,997 B1
• Filed: 12/19/2001
• Issued: 05/18/2010
• Est. Priority Date: 12/19/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Aviani, James Anthony Jr., Starmer, Robert Horst, Dale, Lincoln T., Sylvester, Tim, Gourlay, Douglas Alan
• Primary Examiner(s): Flynn; Nathan
• Assistant Examiner(s): Joo; Joshua
• Application Number:
  US10/034,368
• Time in Patent Office: 3,072 Days
• Field of Search: 709/203, 709/220, 709227-228, 709238-239, 709/245, 790/230, 370/229, 370/238
• US Class Current: 709/245
• CPC Class Codes: H04L 12/5692 Selection among different networks
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Methods and apparatus for processing a service request received from a client are disclosed. When a service request is received, a plurality of packets are transmitted, where each of the plurality of packets identify a different type of service via which to send the corresponding packet. In addition, a mapping of each different type of service to an IP address is preferably maintained, thereby enabling the service request to be processed via an IP address associated with a type of service identified in a first one of the plurality of packets to be received.

Claims

1. A network device adapted for processing a service request, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

receiving a service request;

sending a plurality of response packets in response to receiving the service request, each of the plurality of response packets identifying a different type of service via which to send a corresponding one of the plurality of response packets, wherein the type of service directly corresponds to a Service Provider of the Internet such that each of the plurality of response packets is sent via a different one of a plurality of Service Providers of the Internet;

maintaining a mapping of each different type of service to an IP address, thereby enabling the service request to be processed via an IP address associated with a type of service identified in a first one of the plurality of response packets to be received, wherein the type of service identified in the first one of the plurality of response packets to be received identifies one of the plurality of Service Providers of the Internet; and

providing the IP address of the one of the plurality of Service Providers of the Internet that is mapped to the type of service identified in the first one of the plurality of response packets to be received;

wherein maintaining the mapping comprises maintaining a plurality of A-records, each of the A-records having a type of service field adapted for indicating a type of service that corresponds to one of the plurality of Service Providers of the Internet and wherein receiving the request comprises receiving a DNS A-record request.

2. The network device as recited in claim 1, wherein each of the plurality of response packets is a DNS response.

3. The network device as recited in claim 1, wherein the type of service indicates a specific network connection or domain.

4. In a network device, a method of processing a service request, comprising:

receiving a service request;

sending a plurality of packets in response to receiving the service request, each of the plurality of packets identifying a different type of service via which to send a corresponding one of the plurality of response packets, wherein the type of service identifies a Service Provider of the Internet such that each of the plurality of response packets identifies a different one of a plurality of Service Providers of the Internet; and

maintaining a mapping of each different type of service to an IP address, thereby enabling the service request to be processed via an IP address associated with a type of service identified in a first one of the plurality of packets to be received, wherein the type of service identified in the first one of the plurality of packets to be received identifies one of the plurality of Service Providers of the Internet; and

providing the IP address of the one of the plurality of Service Providers of the Internet that is mapped to the type of service identified in the first one of the plurality of response packets to be received;

wherein maintaining the mapping comprises maintaining a plurality of A-records, each of the A-records having a type of service field adapted for indicating a type of service that corresponds to one of the plurality of Service Providers of the Internet and wherein receiving the request comprises receiving a DNS A-record request.

5. A non-transitory computer-readable medium comprising memory, the computer readable medium storing thereon instructions for processing a service request in a network device, the computer-readable medium storing thereon:

instructions for sending a plurality of response packets in response to receiving a service request, each of the plurality of response packets identifying a different type of service via which to send a corresponding one of the plurality of response packets, wherein the type of service identifies a Service Provider of the Internet such that each of the plurality of response packets identifies a different one of the plurality of Service Providers of the Internet;

instructions for maintaining a mapping of each different type of service to an IP address, thereby enabling the service request to be processed via an IP address associated with a type of service identified in a first one of the plurality of response packets to be received, wherein the type of service identified in the first one of the plurality of response packets to be received identifies one of the plurality of Service Providers of the Internet; and

instructions for providing the IP address of the one of the plurality of Service Providers of the Internet that is mapped to the type of service identified in the first one of the plurality of response packets to be received;

wherein maintaining the mapping comprises maintaining a plurality of A-records, each of the A-records having a type of service field adapted for indicating a type of service that corresponds to one of the plurality of Service Providers of the Internet and wherein receiving the request comprises receiving a DNS A-record request.

6. A network device adapted for processing a service request, comprising:

a processor and a memory;

means for sending a plurality of packets in response to receiving a service request, each of the plurality of packets identifying a different type of service via which to send a corresponding one of the plurality of response packets, wherein the type of service identifies a Service Provider of the Internet such that each of the plurality of response packets identifies a different one of a plurality of Service Providers of the Internet;

means for maintaining a mapping of each different type of service to an IP address, thereby enabling the service request to be processed via an IP address associated with a type of service identified in a first one of the plurality of packets to be received, wherein the type of service identified in the first one of the plurality of packets to be received identifies one of the plurality of Service Providers of the Internet; and

means for providing the IP address of the one of the plurality of Service Providers of the Internet that is mapped to the type of service identified in the first one of the plurality of packets to be received;

wherein maintaining the mapping comprises maintaining a plurality of A-records, each of the A-records having a type of service field adapted for indicating a type of service that corresponds to one of the plurality of Service Providers of the Internet and wherein receiving the request comprises receiving a DNS A-record request.

7. A network device adapted for processing a DNS request, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

receiving a DNS request indicating a domain name for which an IP address is requested;

transmitting a plurality of DNS responses in response to the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet; and

wherein transmitting a plurality of DNS responses comprises transmitting the plurality of DNS responses to a client DNS server associated with a client initiating the DNS request;

wherein the client DNS server is configured to identify a first one of the plurality of DNS responses to be received from the network device and to respond with an IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses, thereby enabling the IP address of the one of the plurality of Service Providers of the Internet via which the first one of the plurality of DNS responses has been received to be provided;

wherein the client DNS server is further configured to obtain the type of service from the first one of the plurality of DNS responses and obtain an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table.

8. The network device as recited in claim 7, wherein each of the plurality of DNS responses has the same source address and destination address.

9. The network device as recited in claim 7, at least one of the processor or the memory being further adapted for:

providing a service identifier in each of the plurality of DNS responses, the service identifier identifying one of the plurality of Service Providers that is to be used to route the corresponding DNS response.

10. The network device as recited in claim 7, wherein each of the plurality of DNS responses comprises a type of service field adapted for indicating a type of service to be used during next-hop based routing based on the type of service.

11. A method of processing a DNS request, comprising:

receiving by a network device a DNS request indicating a domain name for which an IP address is requested;

transmitting by the network device a plurality of DNS responses in response to the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet; and

providing an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted;

wherein transmitting a plurality of DNS responses comprises transmitting the plurality of DNS responses to a client DNS server associated with a client initiating the DNS request;

wherein the client DNS server is configured to identify a first one of the plurality of DNS responses to be received from the network device and to respond with an IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses;

wherein the client DNS server is further configured to obtain the type of service from the first one of the plurality of DNS responses and obtain an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table.

12. The method as recited in claim 11, wherein each of the plurality of DNS responses includes a different one of a plurality of IP addresses, each of the plurality of IP addresses being mapped to a different one of the plurality of Service Providers of the Internet.

13. The method as recited in claim 11, wherein receiving a DNS request comprises receiving a DNS A-record request and wherein transmitting a plurality of DNS responses comprises transmitting a plurality of A-records.

14. The method as recited in claim 13, wherein each of the plurality of A-records includes a different IP address that is mapped to a different one of the plurality of Service Providers of the Internet.

15. The method as recited in claim 14, wherein each of the plurality of A-records further includes a field adapted for identifying the one of the plurality of Service Providers of the Internet.

16. The method as recited in claim 15, further comprising:

maintaining a table of A-records that includes the plurality of A-records.

17. The method as recited in claim 11, wherein transmitting the plurality of DNS responses comprises transmitting the plurality of DNS responses via one or more intermediate routers configured to perform next-hop policy based routing based on the type of service.

18. A non-transitory computer-readable medium comprising memory storing thereon instructions for processing a DNS request in a network device, the computer-readable medium storing thereon the following instructions:

instructions for processing a DNS request that has been received, the DNS request indicating a domain name for which an IP address is requested;

instructions for transmitting a plurality of DNS responses in response to the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet; and

instructions for providing an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted;

wherein transmitting a plurality of DNS responses comprises transmitting the plurality of DNS responses to a client DNS server associated with a client initiating the DNS request;

wherein the client DNS server is configured to identify a first one of the plurality of DNS responses to be received from the network device and to respond with an IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses;

wherein the client DNS server is further configured to obtain the type of service from the first one of the plurality of DNS responses and obtain an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table.

19. A system adapted for processing a DNS request, comprising:

a processor and a memory;

means for receiving a DNS request indicating a domain name for which an IP address is requested;

means for transmitting a plurality of DNS responses in response to the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet; and

means for providing an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted;

wherein transmitting a plurality of DNS responses comprises transmitting the plurality of DNS responses to a client DNS server associated with a client initiating the DNS request;

wherein the client DNS server is configured to identify a first one of the plurality of DNS responses to be received from the network device and to respond with an IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses;

wherein the client DNS server is further configured to obtain the type of service from the first one of the plurality of DNS responses and obtain an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table.

20. A system for selecting an Internet Service Provider via which to process a client request, comprising:

a network device comprising a processor adapted for receiving a DNS request indicating a domain name for which an IP address is requested and transmitting a plurality of DNS responses to a client DNS server associated with a client initiating the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet;

one or more intermediate routers configured to perform next-hop policy based routing based on the type of service; and

a client DNS server associated with a client initiating the DNS request, the client DNS server being configured to identify a first one of the plurality of DNS responses to be received from the network device and to respond to the client with an IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses;

wherein the client DNS server is further configured to obtain the type of service from the first one of the plurality of DNS responses and obtain an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table.

21. A method, comprising:

receiving a plurality of DNS responses from a network device by a client DNS server, the plurality of DNS responses being transmitted by the network device in response to a DNS request indicating a domain name for which an IP address is requested, wherein the client DNS server is associated with a client initiating the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet; and

providing by the client DNS server an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted;

wherein the client DNS server is configured to identify a first one of the plurality of DNS responses to be received from the network device and to respond with an IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses;

wherein the client DNS server is further configured to obtain the type of service from the first one of the plurality of DNS responses and obtain an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table.

22. A method, comprising:

receiving a plurality of DNS responses from a network device by a client DNS server, the plurality of DNS responses being transmitted by the network device in response to a DNS request indicating a domain name for which an IP address is requested, wherein the client DNS server is associated with a client initiating the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet;

identifying by the client DNS server a first one of the plurality of DNS responses to be received from the network device;

obtaining by the client DNS server the type of service from the first one of the plurality of DNS responses to be received from the network device;

obtaining by the client DNS server an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table; and

providing by the client DNS server the IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses, thereby providing an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted.

23. The method as recited in claim 22, wherein each of the plurality of DNS responses includes a different one of a plurality of IP addresses, each of the plurality of IP addresses being mapped to a different one of the plurality of Service Providers of the Internet.

24. The method as recited in claim 22, wherein each of the plurality of DNS responses has the same source address and destination address.

25. The method as recited in claim 22, wherein each of the plurality of DNS responses includes a service identifier in, the service identifier identifying one of the plurality of Service Providers that is to be used to route the corresponding DNS response.

26. The method as recited in claim 22, wherein each of the plurality of DNS responses comprises a type of service field adapted for indicating a type of service to be used during next-hop based routing based on the type of service.

27. The method as recited in claim 22, wherein the DNS request includes a DNS A-record request and each of the plurality of DNS responses includes an A-record.

28. The method as recited in claim 27, wherein each of the plurality of DNS responses includes a different IP address that is mapped to a different one of the plurality of Service Providers of the Internet.

29. The network device as recited in claim 27, wherein each of the plurality of DNS responses includes a field adapted for identifying the one of the plurality of Service Providers of the Internet.

30. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

receiving a plurality of DNS responses from a network device by a client DNS server, the plurality of DNS responses being transmitted by the network device in response to a DNS request indicating a domain name for which an IP address is requested, wherein the client DNS server is associated with a client initiating the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet;

identifying by the client DNS server a first one of the plurality of DNS responses to be received from the network device;

obtaining by the client DNS server the type of service from the first one of the plurality of DNS responses to be received from the network device;

obtaining by the client DNS server an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table; and

providing by the client DNS server the IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses, thereby providing an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted.

31. An apparatus, comprising:

a processor and a memory;

means for receiving a plurality of DNS responses from a network device by a client DNS server, the plurality of DNS responses being transmitted by the network device in response to a DNS request indicating a domain name for which an IP address is requested, wherein the client DNS server is associated with a client initiating the DNS request, each of the plurality of DNS responses being transmitted via a different path associated with a different type of service, wherein the type of service identifies or is mapped to a Service Provider of the Internet such that each of the plurality of DNS responses is transmitted via a different one of a plurality of Service Providers of the Internet;

means for identifying by the client DNS server a first one of the plurality of DNS responses to be received from the network device;

means for obtaining by the client DNS server the type of service from the first one of the plurality of DNS responses to be received from the network device;

means for obtaining by the client DNS server an IP address of the one of the plurality of Service Providers corresponding to the type of service from a mapping table; and

means for providing by the client DNS server the IP address of the one of the plurality of Service Providers of the Internet corresponding to the type of service identified in the first one of the plurality of DNS responses, thereby providing an IP address of the one of the plurality of Service Providers of the Internet via which a first one of the plurality of DNS responses to be received has been transmitted.