US 6,976,087 B1Granted

Service provisioning methods and apparatus

AssigneeRedback Networks Inc.

InventorsRonald Leonard Westfall, Amaranath Sanmugasunderam, Paul Terry, Adam Lorant

Life of this patent

Estimating the term…

Loading patent…

Abstract

Network elements at endpoints of a data connection are identified. A network path is generated between the network elements at the endpoints. The network path is validated by determining whether the network path provides at least one service requirement. The service requirement may be a minimum bandwidth requirement, a maximum bandwidth requirement, a maximum delay requirement, a maximum jitter requirement, a reliability requirement, a requirement that the network path includes network elements capable of acting as security gateways that bracket untrusted sections of the network path, a reachability requirement, or a data collection capability requirement. Network elements along a validated network path are configured to implement the service requirement. In one embodiment, the configuration performed on the network elements is recorded.

Claims35

Dependent claims

A method comprising:

identifying network elements at endpoints of a data connection channel;
generating a candidate path between the network elements at the endpoints;
validating the candidate path by determining whether the candidate path provides at least a service requirement based on a service description describing at least one of:
minimum bandwidth that is to be guaranteed for each data connection,
maximum bandwidth to which each data connection is constrained,
maximum delay that packets in a data connection are allowed to tolerate,
maximum jitter that a data connection is allowed to tolerate,
minimum reliability that each data connection is to be provided,
inclusion of network elements capable of acting as security gateways that bracket untrusted sections of the candidate path,
reachability, and
data collection capability to be instantiated between network locations when the service is in use, and
configuring network elements along a validated candidate path to implement the service requirement;
and
identifying a change in a routing table entry;
identifying data connection channels provisioned on a data link connected to an interface referenced by the routing table entry prior to the change;
for each data connection channel provisioned on the data link, identifying whether the data connection channel is affected by the change;
for each data connection affected by the change, de-provisioning the data connection channel affected by the change;
for each data connection channel affected by the change, re-provisioning the data connection channel affected by the change;
reserving a predetermined percentage of bandwidth for each direction of a data link, wherein reserving the predetermined percentage of bandwidth is to
provide room for manually deployed services,
provide a buffer to accommodate unanticipated network traffic, and
provide a buffer to accommodate one of an imprecisely understood behavior and an imprecise bandwidth control in a router feeding of a data link;
and
determining an effective bandwidth capacity of the data link by subtracting the reserve bandwidth from an available bandwidth associated with the data link.

21 more elements

A method for a provisioning system comprising:

identifying a candidate path for a newly requested service, the newly requested service having a service description, wherein the newly requested service is in an Internet Protocol (IP) network, the IP network having a plurality of routers, wherein the identified candidate path travels through a set of the plurality of routers;
determining whether the set of the plurality of routers can be configured to meet a set of requirements specified by the service description,
generating a graph representing the network, wherein vertices represent routers and links represent data links,
wherein each data link in the candidate path includes an available bandwidth equal or greater than the minimum bandwidth of a corresponding data connection channel,
wherein if any data link in the candidate path does not have an available bandwidth equal or greater than the minimum bandwidth of the corresponding data connection channel, the corresponding available bandwidth equal or greater than the minimum bandwidth of the corresponding data connection channel is removed from the graph representing the network for further consideration,
wherein the minimum bandwidth of the corresponding data connection channel is determined based on a product of the minimum bandwidth described in a corresponding data connection description and the maximum amount of concurrent service usage from the service description, and
wherein the maximum bandwidth of the corresponding data communication channel is determined based on a product of the maximum bandwidth from the corresponding data connection description and the maximum amount of concurrent service usage from the service description;
and
if the set of plurality of routers are determined to meet the set of requirements, then translating the set of requirements into a corresponding set of router management commands to configure each router in the set of the plurality of routers.

6 more elements

A method for a provisioning system comprising:

identifying a set of one or more candidate paths for a newly requested service in an Internet Protocol (IP) network having a plurality of routers, wherein each of the candidate paths travels through a different subset of the plurality of routers, the newly requested service having a service description;
eliminating a candidate path from the set of candidate paths whose corresponding subset of the plurality of routers cannot be configured to meet the set of requirements specified by the service description including a minimum bandwidth required by the service being deployed, wherein the minimum bandwidth is determined based on BWmin=max(BWmax,(Smax/Dmax)),
wherein BWmin represents a minimum bandwidth in bits per second, wherein BWmax represents a required maximum bandwidth from the data connection description in bits per second, wherein Smax represents a maximum size of a packet in bits, and wherein Dmax represents a maximum cross router queuing delay in seconds;
and
translating a remaining candidate path into a set of router management commands to configure the subset of the plurality of routers.

2 more elements

A provisioning system comprising:

a provisioning engine coupled to a network topology database and a provisioned services database, the provisioning engine to identify candidate paths for newly requested services in a network, each of the newly requested services having a corresponding service description that specifies a corresponding set of requirements, wherein each of the candidate paths are to include a subset of routers of a plurality of routers in the network, wherein the provisioning engine is to determine whether a set of the candidate paths meet the corresponding set of requirements including a minimum bandwidth required by the service being deployed, wherein the minimum bandwidth is determined based on BWmin=max(BWmax,(Smax/Dmax)),
wherein BWmin represents a minimum bandwidth in bits per second, wherein BWmax represents a required maximum bandwidth from the data connection description in bits per second, wherein Smax represents a maximum size of a packet in bits, and wherein Dmax represents a maximum cross router queuing delay in seconds;
and
a translation modulate coupled to the provisioning engine, the translation module to translate the set of requirements for a set of candidate paths that meet the corresponding set of requirements, the translation to generate corresponding router management commands to configure routers in the plurality of routers.

1 more element

A machine-readable recording medium storing the instructions that, when executed by a machine, cause the machine to perform operations comprising:

identifying network elements at endpoints of a data connection channel;
generating a candidate path between the network elements at the endpoints;
validating the candidate path by determining whether the candidate path provides at least a service requirement based on a service description describing at least one of:
minimum bandwidth that is to be guaranteed for each data connection,
maximum bandwidth to which each data connection is constrained,
maximum delay that packets in a data connect are allowed to tolerate,
maximum jitter that a data connection is allowed to tolerate,
minimum reliability that each data connection is to be provided,
inclusion of network elements capable of acting as security gateways that bracket untrusted sections of the candidate path,
reachability, and
data collection capability to be instantiated between network locations when the service is in use,
configuring network elements along a validated candidate path to implement the service requirement;
and
identifying a change in a routing table entry;
identifying data connection channels provisioned on a data link connected to an interface referenced by the routing table entry prior to the change;
for each data connection channel provisioned on the data link, identifying whether the data connection channel is affected by the change;
for each data connection affected by the change, de-provisioning the data connection channel affected by the change;
for each data connection channel affected by the change, re-provisioning the data connection channel affected by the change;
reserving a predetermined percentage of bandwidth for each direction of a data link, wherein reserving the predetermined percentage of bandwidth is to
provide room for manually deployed services,
provide a buffer to accommodate unanticipated network traffic, and
provide a buffer to accommodate one of an imprecisely understood behavior and an imprecise bandwidth control in a router feeding of a data link;
and
determining an effective bandwidth capacity of the data link by subtracting the reserve bandwidth from an available bandwidth associated with the data link.

21 more elements

A machine-readable recording medium storing the instructions that when executed by a machine, cause the machine to perform operations comprising:

identifying a candidate path for a newly requested service, the newly requested service having a service description, wherein the newly requested service is in an Internet Protocol (IP) network, the IP network having a plurality of routers, wherein the identified candidate path travels through a set of the plurality of routers;
determining whether the set of the plurality of routers can be configured to meet a set of requirements specified by the service description,
generating a graph representing the network, wherein vertices represent routers and links represent data links,
wherein each data link in the candidate path includes an available bandwidth equal or greater than the minimum bandwidth of a corresponding data connection channel,
wherein if any data link in the candidate path does not have an available bandwidth equal or greater than the minimum bandwidth of the corresponding data connection channel, the corresponding available bandwidth equal or greater than the minimum bandwidth of the corresponding data connection channel is removed from the graph representing the network for further consideration,
wherein the minimum bandwidth of the corresponding data connection channel is determined based on a product of the minimum bandwidth described in a corresponding data connection description and the maximum amount of concurrent service usage from the service description, and
wherein the maximum bandwidth of the corresponding data communication channel is determined based on a product of the maximum bandwidth from the corresponding data connection description and the maximum amount of concurrent service usage from the service description;
and
if the set of plurality of routers are determined to meet the set of requirements, then translating the set of requirements into a corresponding set of router management commands to configure each router in the set of the plurality of routers.

6 more elements

A machine-readable recording medium storing the instructions that, when executed by a machine, cause the machine to perform operations comprising:

identifying a set of one or more candidate paths for a newly requested service in an Internet Protocol (IP) network having a plurality of routers, wherein each of the candidate paths travels through a different subset of the plurality of routers, the newly requested service having a service description;
eliminating a candidate path from the set of candidate paths whose corresponding subset of the plurality of routers cannot be configured to meet the set of requirements specified by the service description including a minimum bandwidth required by the service being deployed, wherein the minimum bandwidth is determined based on BWmin=max(BWmax,(Smax/Dmax)),
wherein BWmin represents a minimum bandwidth in bits per second, wherein BWmax represents a required maximum bandwidth from the data connection description in bits per second, wherein Smax represents a maximum size of a packet in bits, and wherein Dmax represents a maximum cross router queuing delay in seconds;
and
translating a remaining candidate path into a set of router management commands to configure the subset of the plurality of routers.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 09/990,561Filed 21 Nov 2001 · us provisional application
Priority: 24 Nov 2000
Granted: 13 Dec 2005
Term ends: Not estimatedThe source records don’t support an estimate.

Classification16 codes

H04L 43/0852
Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters: delays
H04L 43/087
Delays: jitter
H04L 47/15
Flow control; Congestion control: in relation to multipoint traffic
H04L 47/2441
Traffic characterised by specific attributes, e.g. priority or QoS: relying on flow classification, e.g. using integrated services [IntServ]