Patent ID: 8189481

Claim:
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.