Method and apparatus for a bandwidth broker in a packet network

A method for allocating bandwidth within a network domain by a distributed network server, the distributed network server including a central network server and a plurality of edge network servers, comprising:

• providing a plurality of path-level databases operably coupled to the plurality of edge network servers, the path-level databases including path-level data comprising Quality of Service (QoS) state information for paths within the network domain;
• providing a link-level database operably coupled to the central network server, the link-level database including link-level data comprising QoS information for links in the paths within the network domain, the path-level data being summarized from the link-level data, each of the link connecting two nodes and each of the paths including one or more links;
• receiving by the distributed network server from a network domain edge node operably coupled to an edge network server a flow request for a path within the network domain;
• satisfying by the distributed network server the flow request using the path-level data if the network server determines the distributed network server can satisfy the flow request using the path-level data;
• and
• satisfying by the distributed network server the flow request using the link-level data if the network server determines the distributed network server cannot satisfy the flow request using the path-level data,
• wherein the path-level data includes unused bandwidth allocated to the path and a path state, the method further comprising satisfying by the edge network server the flow request using the unused bandwidth if the path is not in a critical state and the unused bandwidth is sufficient to satisfy the flow request,
• wherein the link-level data further includes quotas of bandwidth available to a link, the method further comprising allocating by the central network server to each link along the path a quota of bandwidth from the quotas of bandwidth available to the link if the path does not have enough unused bandwidth to satisfy the flow request, and
• wherein the link-level data further includes quotas of bandwidth available to a link, the method further comprising allocating by the central network server to each link along the path a quota of bandwidth from the quotas of bandwidth available to the link if the path does not have enough unused bandwidth to satisfy the flow request.

A data processing system adapted to allocate bandwidth within a network domain, comprising:

• a database including path-level data comprising Quality of Service (QoS) information for each path within the network domain and link-level data comprising QoS information for each link within the network domain, the path-level data being summarized from the link-level data, each of the paths comprising a plurality of links;
• a processor;
• and
• a memory operably coupled to the processor and having program instructions stored therein, the processor being operable to execute the program instructions, the program instructions including:
• receiving from a network domain edge node a flow request for a path;
• satisfying the flow request using the path-level data if the flow request can be satisfied using the path-level data;
• and
• satisfying the flow request using the link-level data if the flow request cannot be satisfied using the path-level data,
• wherein the link-level data further includes quotas of bandwidth available to a link, the program instructions further including allocating to each link along the path a quota of bandwidth from the quotas of bandwidth available to the link if the path does not have enough unused bandwidth to satisfy the flow request.

A computer readable medium embodying program instructions for execution by a computer, the program instructions adapting a computer to allocate bandwidth within a network domain, program instructions comprising:

• accessing a database including path-level data comprising path Quality of Service (QoS) infomation and link-level data comprising link Quality of Service (QoS) information for a path within the network domain, each path comprising a plurality of links, the path-level data being summarized from the link-level data of the links of each path;
• receiving from a network domain edge node a flow request for a path;
• satisfying the flow request using the path-level data pertaining to the path if the flow request can be satisfied using the path-level data;
• and
• satisfying the flow request using the link-level data pertaining to the links included in the path if the flow request cannot be satisfied using the path-level data.

A method for allocating bandwidth within a network domain by a bandwidth broker operably coupled to a network domain edge node, comprising:

• accessing a network QoS state database operably coupled to the bandwidth broker, the network QoS state database including:
• path-level data for a path within the network domain, the path level data including unused bandwidth allocated to the path;
• a set of critical links along the path;
• and a path state;
• and
• link-level data for links along the path, the link level data including QoS information for links within the network domain;
• quotas of bandwidth available to a link;
• and a link state;
• receiving a flow request for the path;
• satisfying the flow request using the unused bandwidth if the path is not in a critical state and the path has enough unused bandwidth to satisfy the flow request;
• allocating to each link along the path a quota of bandwidth from the quotas of bandwidth available to the link if the path is not in a critical state and the path does not have enough unused bandwidth to satisfy the flow request;
• and
• allocating bandwidth to each link in the set of critical links from unused bandwidth reclaimed from another path on each link if the path is in a critical state.

A method for allocating bandwidth within a network domain by a network server coupled to a network domain edge node, the network domain including links for connecting two nodes and paths including one or more links for connecting two edge nodes, the method comprising:

• receiving a flow request from the network domain edge node for data flow through a first path, the flow request requiring a flow bandwidth;
• obtaining path-level data for the first path from a database coupled to the network server, the database including link-level data and the path-level data, the link-level data having available bandwidth and reserved bandwidth information for the links within the network domain and the path-level data having available bandwidth and reserved bandwidth information for paths within the network domain, the path-level data being summarized from the link-level data, the link-level data dividing the links into critical links and non-critical links and the path-level data dividing the paths into critical paths and non-critical paths, a critical link being a link having an available bandwidth below a threshold and a critical path being a path including at least one critical link;
• granting the flow request if the flow bandwidth is satisfied by a first bandwidth, the first bandwidth being an available bandwidth of the first path and being obtained from the path-level data;
• obtaining link-level data for all links along the first path if the first path is a non-critical path and if the flow bandwidth is not satisfied by the first bandwidth;
• requesting more available bandwidth for all the links along the first path;
• obtaining link-level data for the at least one critical link along the first path if the first path is a critical path;
• requesting more available bandwidth for the at least one critical link and for the non-critical links to obtain a second bandwidth for the first path;
• updating the available bandwidth of the first path in the path-level database;
• granting the flow request if the flow bandwidth is satisfied by the second bandwidth;
• and
• rejecting the flow request if the requesting more available bandwidth for any of the links is rejected.

A method for dynamic allocation of bandwidth within a network domain having nodes including core nodes and edge nodes, a link connecting two nodes, a path connecting two edge nodes and including one or more links, each link belonging to no paths, one path, or more than one paths, data flowing from a first edge node to a second edge node through a path connecting the first edge node to the second edge node, the method comprising:

• dividing total bandwidth of each link into a plurality of quotas, a quota being a discrete amount of bandwidth larger than an average bandwidth requirement of data flow in the network domain;
• dividing the plurality of quotas of each link among the one or more paths passing through the link and including the link by allocating one quota to each path;
• maintaining a link state of each link, the link state being a critical state if available bandwidth of the link is below a threshold value and otherwise being a normal state, a link in the critical state being a critical link and a link in the normal state being a normal link;
• maintaining a path state of each path, the path state being a critical path state if the path includes at least one critical link, a path in the critical path state being a critical path;
• maintaining bandwidth use of each path, each path having a reserved bandwidth and an available bandwidth, a sum of the reserved bandwidth and the available bandwidth equaling a total path bandwidth;
• receiving a flow request through a first path for a first data flow requiring a first data bandwidth;
• if the first path is not a critical path and if available bandwidth on the first path is not smaller than the first data bandwidth, granting the flow request;
• allocating more quotas to all of the links of the first path if the first path is not a critical path and if the available bandwidth of the first path is smaller than the first data bandwidth and granting flow request if the available bandwidth of the first path is no longer smaller than the first data bandwidth;
• allocating more quotas to the one or more critical links of the first path if the first path is a critical path and granting flow request if the first path is no longer a critical path and if available bandwidth on the first path is not smaller than the first data bandwidth;
• and
• rejecting the flow request if sufficient number of quotas are not available for allocating more quotas to the critical links or to the normal links and if the first path is a critical path or if the available bandwidth of the first path is smaller than the data bandwidth.

A method for dynamic allocation of bandwidth within a network domain having nodes including core nodes and edge nodes, a link connecting two nodes, a path connecting two edge nodes and including one or more links, each link belonging to no paths, one path, or more than one paths, data flowing from a first edge node to a second edge node through the path connecting the first edge node to the second edge node, the method comprising:

• dividing total bandwidth of each link into a plurality of quotas, a quota being a discrete amount of bandwidth larger than an average bandwidth requirement of data flow in the network domain;
• dividing the plurality of quotas of each link among the paths passing through the link and including the link by allocating one quota to each path;
• maintaining a link state of each link, the link state being a critical state if available bandwidth of the link is below a threshold value and otherwise the link state being a normal state, a link in the critical state being a critical link and a link in the normal state being a normal link;
• maintaining bandwidth use of each link, each link having a reserved bandwidth and an available bandwidth, a sum of the reserved bandwidth and the available bandwidth equaling a total link bandwidth;
• maintaining a path state of each path, the path state being a critical path state if the path includes at least one critical link, a path in the critical path state being a critical path;
• receiving a flow request from a first path for data flow through a first link, the flow request requiring a flow bandwidth;
• rejecting the flow request if the first link is a critical link;
• if the first link is not a critical link, collecting residual bandwidth of the all the paths including the first link by obtaining a sum of the quotas of the first link allocated to each of the paths including the first link and subtracting the sum from a total bandwidth of the first link to obtain an available bandwidth for the first link;
• if the available bandwidth of the first link is smaller than the flow bandwidth, rejecting the flow request;
• and
• if the available bandwidth of the first link is not smaller than the flow bandwidth,
• granting the flow request,
• decreasing the available bandwidth of the first link by one quota, and
• if the available bandwidth minus the flow bandwidth is below the threshold value, updating the link state of the first link and the path state of the paths including the first link to the critical state,
• wherein the flow request is a request for a quota on the first link or a request for a data flow rate.