Adaptive routing of network traffic
First Claim
1. A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps ofgenerating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair,over predetermined periods, measuring link data to estimate an equivalent offered load for each link, said equivalent offered load for each link being given by the ratio φ
- /(1-α
), where φ
is the carried load and α
is the blocking, as obtained from measured link data, and computing route occupancy factors based on said equivalent offered load,upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, andif the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value;
otherwise, blocking the service request.
6 Assignments
0 Petitions
Accused Products
Abstract
A process is disclosed for adaptively routing service requests through a network comprising nodes interconnected with links. The network is also arranged so that each node may communicate with each of the other nodes. At preselected time intervals, sets of routes through the network are generated in response to the network configuration and traffic information. Over predetermined periods, traffic data is measured to determine carried load and blocking for each link. Also, at predetermined time intervals, occupancy factors are computed as determined by the network configuration and in response to traffic information including measured traffic data. Each of the occupany factors is derived from a nominal routing scheme in which a call blocked on a single route is treated as a lost call as in separable routing. Upon a request for service, the occupany factors corresponding to the busy-idle status of the links are used to compute an occupany value associated with each of the routes. Each route is converted to a candidate route based on traffic load at the initiation of the service request. The minimum occupany value for each set of routes is selected as the candidate route for bridging a given node pair. If this minimum value is less than a preselected threshold, the traffic is routed over this candidate route, thereby satisfying the service request. Otherwise, the request is denied.
-
Citations
8 Claims
-
1. A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of
generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, over predetermined periods, measuring link data to estimate an equivalent offered load for each link, said equivalent offered load for each link being given by the ratio φ - /(1-α
), where φ
is the carried load and α
is the blocking, as obtained from measured link data, and computing route occupancy factors based on said equivalent offered load,upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value;
otherwise, blocking the service request. - View Dependent Claims (2)
- /(1-α
-
3. A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of
generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, over predetermined periods, measuring link data to estimate an equivalent offered load for each link and computing route occupancy factors based on said equivalent offered load, said occupancy factors being given by the Δ - (k,j) factors obtained from the relation ##EQU3## where B is the Erlang-B formula, sk is the number of potential servers in link k, 0<
j<
sk and yk is the equivalent offered load for each link k,upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value;
otherwise, blocking the service request. - View Dependent Claims (4, 5, 6)
- (k,j) factors obtained from the relation ##EQU3## where B is the Erlang-B formula, sk is the number of potential servers in link k, 0<
-
7. A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of
generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, initially computing route occupancy factors using a presumed set of nominal link loads in order to service requests received prior to the first estimate of an equivalent offered load, over predetermined periods, measuring link data to estimate said equivalent offered load for each link and computing route occupancy factors based on said equivalent offered load, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; - otherwise, blocking the service request.
- View Dependent Claims (8)
Specification