Method of Routing a Request for a Virtual Circuit Based on Information From Concurrent Requests

The invention relates to the routing of multiple virtual circuits in networks.

Computer networks are a principal means of exchanging or transferring information (e.g. data, voice, text, video, etc.) among host machines connected to the network. The network comprises nodes connected, to each other and to the hosts, by links. Typically, each link is bidirectional, i.e. information may be conveyed in forward and reverse directions, and each link is characterized by a bandwidth capacity in each direction.

An important consideration in network operation is how the information is routed. When information is to be exchanged between two particular hosts, a bidirectional path is established in the network between them. Typically, the path that is established is a so-called "virtual circuit" (VC), by which it is meant that a host simply specifies the destination for the information, and the network delivers the information as though a circuit is connected to the destination. One of many different routes and techniques could be selected to deliver the information, but the particular selection is of no concern to the host. The task of routing is to select the nodes and links between the nodes that comprise the path taken by the VC so as to efficiently utilize network resources, e.g. route as many VCs as possible without exceeding the bandwidth capacity of any particular link. This is often achieved by selecting a path so as to minimize some cost function that reflects the amount of network resources required by the selected path. Although a variety of cost functions can be used, cost functions typically take into account the current network state (i.e., the network topology and current allocation of network resources), delay through the network, etc. Importantly, the routing problem is often further complicated in that the routing must be effectuated "on-line," i.e. without knowledge of what effect future routing demands will have on network resources. Although this problem may be solved by so-called "dynamic-rerouting" techniques, these techniques typically adversely affect the quality of service offered to users of the network.

Many techniques for routing VCs have been suggested. One such technique is minimum hop routing in which the path going through the smallest number of nodes is selected. Another techniques that has been suggested employs exponential cost functions and scaling, has been suggested. See, J. Aspnes et al., "On-Line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing," Proc. 23rd Annual Symp. on Theory of Computing, San Diego, Calif., May 1993. In the scaling technique, a portion .gamma. of the bandwidth capacity of each link is initially allocated, and a cost function is computed for routing a path given that allocated bandwidth. When routing can no longer be achieved in the network with that allocated bandwidth, more bandwidth can be allocated, i.e. .gamma. is increased. Typically, the function for determining the cost for a given link in a path for the requested VC is C.sub..iota. (.chi.,.DELTA..chi.)=.alpha..sup..gamma..chi..sbsp..iota..sup.+.gamma..DEL TA..chi..sbsp..iota. -.alpha..sup..gamma..chi..sbsp..iota. where C.sub..iota. (.chi.,.DELTA..chi.) is the cost for link .iota. in the path, .alpha. is a constant, .chi..sub..iota. is the fraction of the bandwidth capacity of the link that is in use and .DELTA..chi..sub..iota. is the fraction of the bandwidth capacity of the link that is requested by the VC.

These routing techniques, however, have shortcomings. In particular, it is recognized that previous routing methods do not take into account information available in a "multiple VC request" situation. In such a situation, at any given time, the network may have received two or more concurrent requests to establish VCs. Prior methods simply respond to one of the multiple requests for a VC and route the requested VC, e.g. according to a first-come, first-served discipline, without checking to determine the demands of the other requests. Thus, the routing is truly of the "on-line" type described above even though the network does have some information about what further network routing demands will be as a result of the fact that other requests were concurrently received.

In accordance with the present invention, then, it is recognized that in routing a request for a virtual circuit that information about concurrently requested virtual circuits may advantageously be used. Accordingly, a method is disclosed for routing a set of concurrent requests for virtual circuits, wherein each virtual circuit request is specified by one or more parameters, by routing each request in the set as a function of one or more parameters of a plurality of the requests. In one embodiment of the invention a set of concurrent requests is ordered according to one or more of the parameters, and the requests are then routed in that order. In accordance with a feature of the invention, the routing may be refined by using a local search to exploit to a greater extent the information available from multiple requests for virtual circuits.

Other features and advantages of the invention will become apparent from the following detailed description taken together with the drawings in which:

FIG. 1 illustrates a centralized routing network in which the invention may be practiced.

FIG. 2 is a flowchart of the steps in the preferred embodiment.

FIG. 3 is a flowchart of steps of a local search feature of the invention.

FIG. 4 illustrates a distributed routing network in which the invention may be practiced.

FIG. 1 illustrates the structure of a network in which the invention may be practiced. Hosts 102-i,i=1,2, . . . , exchange information via network 106. Network 106 comprises links 110-k,k=1,2, . . . , connecting nodes 108-j,j=1,2, . . . , to each other and to hosts 102-i. A pair of nodes may be connected by one or more links.

Network 106 in FIG. 1 is a centralized routing system in that network 106 utilizes complete information for routing through use of centralized routing request processor 111. Request processor 111 is connected to hosts 102-i,i=1,2, . . . and to complete information about the network state. Thus, the cost for any path (i.e. the additional network resources required for any path) through the network can be determined, and, using the inventive method described below, all VCs in network 106 of FIG. 1 can be routed efficiently with respect to a given criterion, e.g. maximizing the total amount of bandwidth routed.

FIG. 2 is a flowchart of an illustrative routing method with which the present invention may be used. In step 200 of FIG. 2 at any given time, the network must respond to set of i.sub.max, i.sub.max =0,1,2, . . . , requests for establishing VCs. Each individual request, VC.sub.req.sup.i, i=1, . . . i.sub.max is specified by one or more parameters. For example, each VC.sub.req.sup.i may be specified by the source host S.sup.i, destination host D.sup.i, bandwidth requested in the forward direction B.sub.f.sup.i and bandwidth requested in the reverse direction B.sub.r.sup.i. Thus,

In step 205 of FIG. 2 the information available in the multiple VC request situation is used in routing. Specifically, for each individual request in the set of requests, a path is selected according to function of one or more parameters of a plurality of requests in the set. One illustrative embodiment of the method is described in co-pending application "A Method of Permanent Virtual Circuit Routing," filed concurrently herewith, commonly assigned and hereby incorporated by reference. This embodiment routes permanent VCs (i.e. VCs designed to operate and remain established for time periods on the order of years, as opposed to switched VCs which are designed to operate for hours or days) by first ordering the requests according to a parameter of the requests, e.g. bandwidth, and then using an exponential cost function to route the requests. The ordering process first routes those requests requiring the most network resources according to a cost function and thus requiring the most flexibility in routing. If an objective in the routing is to conserve bandwidth, it is advantageous to order VC.sub.req.sup.i in decreasing order of total requested bandwidth (forward and reverse) so that those requests requiring large bandwidths can be accommodated without increasing the risk of exceeding the bandwidth capacity of any link.

Those skilled in the art will now recognize that the information available in the multiple (switched or permanent) VC request situation may be used in a variety of ways and with a variety of, i.e. not necessarily exponential, cost functions. For example, the requests can be routed on a first-come, first-served basis but with knowledge of what the average bandwidth requirement is of the requests in the set of requests. Thus, when a particular request is routed, the cost function for the routing may reflect whether the request requires a large or small amount of bandwidth relative to other requests in the set thereby routing relatively small bandwidth requests on links already near capacity so as to conserve bandwidth on other links for large bandwidth requests.

Returning to step 205, once a set of paths P is determined, an optional local search may be performed, as described below, to refine the set of path selections. In step 275 of the method of FIG. 2, the set of requests are routed on the set of path P.

The optional local search of step 265 can be used to refine the selection of paths so that the total cost of routing all VCs can be reduced. The steps in one embodiment of the local search of step 265 are illustrated in the flowchart of FIG. 3. In step 305 variables are initialized. In particular, P is defined as the set of paths {p1,p2, . . . ,pi.sub.max } associated with the i.sub.max VC requests as determined by a routing method, e.g. the method of FIG. 2. The current set of best paths for routing is stored in P.sup.* and the cost of routing that current set of best paths is C.sup.*. Initially, P.sup.* =P and C.sup.* =C(P) where C is a second cost function, described below, which determines the cost of routing all the VC.sub.req.sup.i. In step 310 a flag, called impflag, is set to zero and a counter i,i=1,2 . . . i.sub.max, is set to 1.

In step 315 a particular VC.sub.req.sup.i and its associated path p.sub.i are selected. For illustrative purposes in FIG. 3 the VC.sub.req.sup.i are selected in increasing order of i. For the selected i a search is made for a lowest cost path p.sup.* for routing VC.sub.req.sup.i (using, for example, Cost.sup.1) assuming all other VC.sub.req.sup.i are routed as in the set P. A new set of paths, P, is formed in step 320 by setting P to P except for the selected p.sub.i which is set to p.sup.*. In step 330 if C(P)<C.sup.*, then P.sup.* and C.sup.* are set to P and C(P), respectively, and impflag is set to one.

Steps 315-340 are repeated for each successive VC.sub.req.sup.i. When all i,i=1,2, . . . i.sub.max, have been examined for potential rerouting, impflag is checked to see if any improvement in routing is possible. If impflag is zero, no alternative routing of any one VC.sub.req.sup.i will reduce the cost of routing all VC.sub.req.sup.i, and the search is ended. As indicated in step 345, if impflag has been set to one, there exists an alternative routing (i.e. a new shortest path) for one VC.sub.req.sup.i that results in the greatest reduction in routing cost. In step 355, that new lowest cost path, reflected in P.sup.*, becomes P. The VC.sub.req.sup.i are now to be routed according to P.sup.* at cost C(P.sup.*). Steps 310-355 are repeated until no new paths are found that reduce the cost.

The second cost function may advantageously be selected as ##EQU1## where the variables in the equation are defined as for equation 1 and where the sum in each exponential and in the linear term is over all VC.sub.req.sup.i such that their associated path uses the link in the outer summation. Thus, the second cost function gives the total cost of routing multiple VC.sub.req.sup.i on their associated paths.

The steps in FIG. 3 reflect a so-called "greedy" heuristic in which each possible alternative path for each VC.sub.req.sup.i is examined to see which alternative path, if any, reduces the cost of routing by the greatest amount. That alternative path is then selected as the new path associated with the VC. The process is repeated until no alternative path for any VC.sub.req.sup.i will reduce the cost of routing all the requests. Those skilled in the art will recognize that other local searches utilizing other search criteria can be used. For example, instead of searching through all the alternative paths to find the one that reduces the cost of routing all VC.sub.req.sup.i the most, it may be sufficient simply to find a first alternative path that reduces costs by any amount. Then the search could simply go onto the next VC.sub.req.sup.i. This "less greedy" heuristic searches the solution space differently and can potentially converge to a better "local minimum" than the "greedy" heuristic. This is highly dependent on the list of VC.sub.req.sup.i being routed and the current state of the network.

FIG. 4 illustrates the structure of a distributed network 416, comprising nodes 418-m and links 420-n, in which the inventive method may be practiced. Network 416 is a distributed routing system in that each node 418-m periodically exchanges state information. The state information reflects the amount of network resources available or in use on a link from a node to every neighboring node. Thus, the cost for any path through the network can be determined. However, unless the state information propagates quickly relative to the speed with which VCs are established and torn down, the information will be incomplete (e.g. dated). Thus, each node may have a different description of the network state, and this description is called the local network state. The methods described above can be used in a distributed routing system except that incomplete state information (i.e. the local network state) is used. Note however, the paths determined based on the incomplete information may no longer be available (e.g. the capacity of a link may have become exhausted since the most recent state information was received) when the VC is actually to be routed (as for example in the routing of step 275 of FIG. 2). Requests for VCs that are not successfully routed, e.g. those requests for which the selected path is not available, may be included in the next set of requests or may form a new set of requests. Note further that it is advantageous when routing in a distributed routing system not to update the local network state until an entire set of requests has been routed. This ensures that procedures, such as the search routine of FIG. 3, will terminate.

This disclosure describes a method of routing multiple virtual circuit requests using information available in the multiple VC request situation. The method disclosed herein have been described without reference to specific hardware or software. Instead, the method has been described in such a manner that those skilled in the art can readily adapt such hardware and software as may be available or preferable for particular application.