A system, device, and method for supporting virtual private networks in a label switched communication network utilizes an extended Next Hop Resolution Protocol in order to establish a label switched path for a particular virtual private network. Specifically, label information and a corresponding virtual private network identifier are carried in certain Next Hop Resolution Protocol messages. A label request and a corresponding virtual private network identifier is carried in Next Hop Resolution Protocol Resolution Request messages that are forwarded hop-by-hop by a number of devices along a forward path. Label mapping information and a corresponding virtual private network identifier are carried in Next Hop Resolution Protocol reply messages that are forwarded hop-by-hop by the devices in the forward path. In various embodiments of the invention, the label information and the corresponding virtual private network identifier may be carried in a type-length-value field, and the Next Hop Resolution Protocol reply messages may be Next Hop Resolution Protocol Resolution Reply messages or novel Next Hop Resolution Protocol Label Mapping messages.