Using the interface, e.g., from one of the client devices 1142A, a client may submit a request for dedicated connectivity, e.g., over a path 1175 that may include links of the public Internet. The request may, for example, include the physical address or addresses at which the client desires dedicated connectivity. In response to the request, the connectivity coordinator may be operable to identify one or more LMCPs 1150 that may be available to establish dedicated connections between the provider network 1100 and the requesting client's network (e.g., 1162A), and generate and transmit a response that lists the selected LMCP or LMCPs. The selected LMCP may operate or manage one or more routers that happen to be co-located with one of the endpoint routers 1132 of the provider network 1100, or may have the ability to set up such routers if they are not already available. In some embodiments the connectivity coordinator 1114 may allow the client to select one LMCP from among a set of available LMCPs, while in other embodiments the connectivity coordinator 1114 may determine the specific LMCP or LMCPS that should be used, and inform the client of the determination. Later, after the dedicated connectivity has been set up, for example via steps similar to those outlined in FIG. 2, the connectivity coordinator 1114 may in some embodiments provide a confirmation to the client indicating that the desired connectivity has been verified. The interface may be used for communication between the client and the connectivity coordinator 1114 during any of the stages of dedicated connectivity establishment and use—e.g., a client may query the state of a requested connection or an established connection using the interface, and may request various connectivity modifications, disabling and enabling of connectivity, and the like. Responses to the client requests may also be formatted in accordance with the interface.