QoS-based routing for CE-based VPN
View Patent ↗CE devices of the present invention are enabled to make more judicious routing decisions in CE-based VPNs. In determining a next-hop in a path from a source CE to a destination subnet, CE-to-CE costs are associated with each next-hop CE in a plurality of next-hop CEs. Each CE-to-CE cost is a cost of a path from the source CE to the associated next-hop CE. CE-to-subnet costs are associated with each of the next-hop CEs. Each CE-to-subnet cost is a cost of a path from the associated next-hop CE to the destination subnet. Total-costs are associated with each of the next-hop CEs. Each total-cost is a sum of a CE-to-CE cost associated with a next-hop CE and a CE-to-subnet cost associated with the same next-hop CE. The next-hop in the path is set to be a next-hop CE associated with an associated total-cost.
1. A method for determining a next-hop in a path from a source customer edge device (“source CE”) of a CE-based Virtual Private Network (“VPN”) through a service provider (SP) network to a destination subnet of the CE-based VPN, the CE-based VPN being unknown to any SP device of the SP network in the path handling traffic of the CE-based VPN, the method comprising:
associating one or more CE-to-CE costs with each next-hop CE in a plurality of next-hop CEs, each CE-to-CE cost being a cost of a path from the source CE of the CE-based VPN to one of the associated next-hop CEs;
associating one or more CE-to-subnet costs with each of the next-hop CEs, each CE-to-subnet cost being a cost of a path from one of the associated next-hop CEs to the destination subnet;
associating one or more total-costs with each of the next-hop CEs, each total-cost being a sum of a CE-to-CE cost associated with next-hop CE and a CE-to-subnet cost associated with the same next-hop CE;
setting a next-hop in a path through the SP network from the source CE to the destination subnet to be a next-hop CE associated with an associated total-cost; and
automatically discovering CEs using an auto-discovery mechanism via Multiprotocol extensions for Border Gateway Protocol (“MP-BGP”), wherein the auto-discovery mechanism is executed over secure control channels established using a unique Group Security Association (“GSA”), wherein the CE-based VPN includes at least a portion of the CEs that lack DiffServ capability, wherein setting the next-hop in the path through the SP network to be the next-hop CE associated with the associated total-cost comprises setting the next-hop in the path from the source CE to the destination subnet of the CE-based VPN, wherein associating one or more total-costs with each of the next-hop CEs comprises the associated total cost being a sum of a cost metric representing delay along links of a path.
2. The method of claim 1 , wherein the set next-hop is a next-hop CE associated with the least of all associated total costs.
3. The method of claim 1 , wherein CE-to-CE costs, CE-to-subnet costs, and total-costs are delay metrics.
4. The method of claim 1 , wherein associating one or more CE-to-subnet costs comprises executing the auto-discovery mechanism via the MP-BGP.
5. The method of claim 1 , wherein associating one or more CE-to-CE costs comprises receiving topology information from a service provider.
6. The method of claim 1 , wherein each associated CE-to-CE cost is a worst cost, wherein associating one or more CE-to-CE costs comprises employing a probing technique.
7. The method of claim 1 , wherein each associated CE-to-CE cost comprises a single constant-cost, wherein the constant-cost is a worst-case cost for traversing paths between any two CEs in the CE-based VPN.
8. The method of claim 1 , further comprising:
receiving a cost matrix from an SP device at a given CE, the cost matrix representing costs to transmit data from one CE to another CE within the CE-based VPN, wherein each CE includes CE-to-CE costs for traversing the SP network from the source CE to a next-hop CE;
identifying a predetermined maximum acceptable total-cost for a path between the source CE and the destination subnet; and
identifying multiple next-hop CEs, each next-hop CE of the multiple next-hop CEs having a total-cost below the predetermined maximum acceptable total-cost of the path between the source CE and the destination subnet, the multiple next-hop CEs including one CE having a least total-cost,
wherein setting a next-hop in a path includes selecting a next-hop CE from the multiple next-hop CEs, having a total-cost below the predetermined maximum acceptable total cost of the path between the source CE and the destination subnet, other than the one CE having the least total-cost,
wherein the CE-based VPN establishes a secure key management channel and a secure control channel using a group controller/key server and a single Internet Protocol Security (“IPSec”) Security Association (“SA”) for site-to-site communication.
9. The method of claim 1 , further comprising
identifying a worst-case cost, for traversing core network as a CE-to-CE cost, by traversing the core network from one given CE to another given CE using a probing technique that determines the worst-case cost between two given CEs, the probing technique using a trace-route to find an upper bound worst-case cost; and
building a cost matrix using the probing technique for pairs of CEs so that each CE builds a respective cost matrix for each connection a given CE has with the core network,
wherein the next-hop CE associated with the associated total-cost is a next-hop CE associated with a least of all associated total costs, the least of all associated total costs being a minimal-cost path from the source CE to the destination subnet,
wherein the CE-based VPN establishes a secure key management channel and a secure control channel using a group controller/key server and a single Internet Protocol Security (“IPSec”) Security Association (“SA”) for site-to-site communication.
10. The method of claim 1 , further comprising:
identifying a worst-case cost, for traversing core network as a CE-to-CE cost, by traversing the core network from one given CE to another given CE being a constant cost, the constant cost being a worst-case cost for traversing the core network between two given subnets, the constant cost being used as a CE-to-CE cost associated with each next-hop CE, to build a cost matrix,
wherein the next-hop CE associated with the associated total-cost is a next-hop CE associated with a least of all associated total costs, the least of all associated total costs being a minimal-cost path from the source CE to the destination subnet; and,
wherein the CE-based VPN establishes a secure key management channel and a secure control channel using a group controller/key server and single Internet Protocol Security (“IPSec”) Security Association (“SA”) for site-to-site communication.
11. A source customer edge device (“source CE”) of a CE-based Virtual Private Network (“VPN”) in communication with a service provider (SP) network that carries traffic of the CE-based VPN from the source CE to a destination subnet of the CE-based VPN, the CE-based VPN being unknown to any SP device of the SP network in a path handling traffic of the CE-based VPN, the source CE comprising:
a microprocessor; and
a memory coupled to the processor, the memory storing instructions that, when executed by the processor, cause the source CE to perform the operations of:
associating one or more CE-to-CE costs with each next-hop CE in a plurality of next-hop CEs, each CE-to-CE cost being a cost of a path from the source CE to one of the associated next-hop CEs;
associating one or more CE-to-subnet costs with each of the next-hop CEs, each CE-to-subnet cost being a cost of a path from one of the associated next-hop CEs to the destination subnet;
associating one or more total-costs with each of the next-hop CEs, each total-cost being a sum of a CE-to-CE cost associated with a next-hop CE and a CE-to-subnet cost associated with the same next-hop CE;
setting a next-hop in a path through the SP network from the source CE to the destination subnet to be a next-hop CE associated with an associated total-cost; and
automatically discovering CEs using an auto-discovery mechanism via Multiprotocol extensions for Border Gateway Protocol (“MP-BGP”), wherein the auto-discovery mechanism is executed over secure control channels established using a unique Group Security Association (“GSA”), wherein the CE-based VPN includes at least a portion of the CEs that lack DiffServ capability, wherein setting the next-hop in the path through the SP network to be the next-hop CE associated with an associated total-cost comprises setting the next-hop in the path from the source CE to the destination subnet of the CE-based VPN, wherein associating one or more total-costs with each of the next-hop CEs comprises the associated total cost being a sum of a cost metric representing delay along links of a path.
12. The source customer edge device of claim 11 , wherein the set next hop is a next-hop CE associated with the least of all associated total costs.
13. The source customer edge device of claim 11 , wherein CE-to-CE costs, CE-to-subnet costs, and total-costs are delay metrics.
14. The source customer edge device of claim 11 , wherein associating one or more CE-to-subnet costs comprises executing the auto-discovery mechanism via the MP-BGP.
15. The source customer edge device of claim 11 , wherein associating one or more CE-to-CE costs comprises receiving topology information from a service provider.
16. The source customer edge device of claim 11 , wherein each associated CE-to-CE cost is a worst cost, wherein associating one or more CE-to-CE costs comprises employing a probing technique.
17. The source customer edge device of claim 11 , wherein each associated CE-to-CE cost comprises a single constant-cost, wherein the constant-cost is a worst-case cost for traversing paths between any two CEs in the CE-based VPN.
18. A customer edge (CE)-based Virtual Private Network (“VPN”), comprising:
a plurality of customer edge devices (“CEs”) in communication with a service provider (SP) network that carries traffic of the CE-based VPN, the CE-based VPN being unknown to any SP device of the SP network in a path carrying the traffic of the CE-based VPN;
a destination subnet; and
at least one source CE comprising:
a microprocessor; and
a memory coupled to the processor, the memory storing instructions that, when executed by the processor, cause the at least one source CE to perform the operations of:
associating one or more CE-to-CE costs with each next-hop CE in a plurality of next-hop CEs, each CE-to-CE cost being a cost of a path from the at least one source CE to one of the associated next-hop CEs;
associating one or more CE-to-subnet costs with each of the next-hop CEs, each CE-to-subnet cost being a cost of a path from one of the associated next-hop CEs to the destination subnet;
associating one or more total-costs with each of the next-hop CEs, each total-cost being a sum of a CE-to-CE cost associated with a next-hop CE and a CE-to-subnet cost associated with the same next-hop CE;
setting a next-hop in a path through the SP network from the at least one source CE to the destination subnet to be a next-hop CE associated total-cost; and
automatically discovering CEs using an auto-discovery mechanism via Multiprotocol extensions for Border Gateway Protocol (“MP-BGP”), wherein the auto-discovery mechanism is executed over secure control channels established using a unique Group Security Association (“GSA”), wherein the CE-based VPN includes at least a portion of the CEs that lack DiffServ capability, wherein setting the next-hop in the path through the SP network to be the next-hop CE associated with the associated total-cost comprises setting the next-hop in the path from the at least one source CE to the destination subnet, wherein associating one or more total-costs with each of the next-hop CEs comprises the associated total cost being a sum of a cost metric representing delay along links of a path.
19. The VPN of claim 18 , wherein associating one or more CE-to-subnet costs comprises executing the auto-discovery mechanism via the MP-BGP.