Network congestion reduction using boolean constrained multipath routing

Abstract

A packet routing method includes computing, for a source node in the data network and a destination node in the data network, a set of multiple routes providing a set of shortest routes from the source to the destination that satisfy all the truth assignments for the Boolean algebra available from the path in the network. The method selects, for a packet flow, a route where logical conjunction of the policy constraints of the flow and the route is satisfied and where the route has sufficient bandwidth.

Claims

1. A method of routing traffic within a data network by network routing equipment, the network comprising a set of policy constraints, the method comprising: a) identifying from a flow, a set of flow-specific constraints; b) computing a best set of routes from a source node to a destination node in the network, wherein the routes in the best set of routes satisfy the entire set of policy constraints in the network; c) selecting a subset from the best set of routes wherein the subset comprises routes that meet the set of flow-specific constraints; d) selecting a least congested route from the subset, where the policy constraint comprises a Boolean constraint; and where the Boolean constraint comprises a selected internet protocol field, a selected network zone, a selected user identification, a selected operating system, a selected application, a selected facility or user security clearance, a selected level of content sensitivity, selected physical layer attributes, a selected time, or a selected threat level.

2. The method of claim 1 where the set of policy constraints comprises a performance constraint.

3. The method of claim 2 where the performance constraint comprises a selected hop count, a selected delay, a selected bandwidth, or a selected reliability.

4. The method of claim 1 where the flow specific constraint comprises a performance constraint.

5. The method of claim 4 where the performance constraint comprises a selected hop count, a selected delay, a selected bandwidth, or a selected reliability.

6. The method of claim 1 where the flow specific constraint comprises a Boolean constraint.

7. The method of claim 6 where the Boolean constraint comprises a selected internet protocol field, a selected network zone, a selected user identification, a selected operating system, a selected application, a selected facility or user security clearance, a selected level of content sensitivity, selected physical layer attributes, a selected time, or a selected threat level.

8. The method of claim 1 where one or both of the set of policy constraints and the flow-specific constraints can be selected by a network user or administrator.

9. A method of routing traffic within a data network by network routing equipment, the network comprising a set of policy constraints, the method comprising: a) identifying from a flow, a set of flow-specific constraints; b) computing a best set of routes from a source node to a destination node in the network, wherein the routes in the best set of routes satisfy the entire set of policy constraints in the network; c) selecting a subset from the best set of routes wherein the subset comprises routes that meet the set of flow-specific constraints; d) selecting a least congested route from the subset; where the flow specific constraint comprises a Boolean constraint; and where the Boolean constraint comprises a selected internet protocol field, a selected network zone, a selected user identification, a selected operating system, a selected application, a selected facility or user security clearance, a selected level of content sensitivity, selected physical layer attributes, a selected time, or a selected threat level.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a part of a network where the number of hops between routing devices varies and where each device does or does not satisfy a particular Boolean test. Routing based on just one Boolean test per device will not be suitable for all application types.

(2) FIGS. 2A and 2B show a pair of truth tables corresponding to FIG. 1.

(3) FIG. 3 shows routing table entries computed for a BCMR routing algorithm.

(4) FIG. 4 shows for different routes the truth assignments to variables in Boolean constraints of FIG. 3.

(5) FIG. 5 is a schematic diagram illustrating data structures used by a routing method according to an embodiment of the present invention.

(6) FIG. 6 is an outline of the steps of a method for packet routing according to one embodiment of the invention.

(7) FIG. 7 is a schematic diagram illustrating a portion of a network including multiple router devices and a central network controller device, according to one embodiment of the invention.

(8) FIG. 8 is a schematic diagram illustrating classification of traffic flows in a network router device according to an embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

(9) Internet routing is based on use of the best path to a given destination. This best-path model limits communication applications to the use of a single-path in an Internet environment. Furthermore, the predominant use of destination-based forwarding in the Internet is a particularly aggressive form of single-path communication. With destination-based forwarding, the path used to carry traffic through an intermediate node to a destination must be an extension of the path from the intermediate node to the destination. This strong tendency for traffic to be concentrated on a subset of available paths results in inefficient use of network resources with traffic experiencing congestion while network resources are still idle. Modern use of the Internet involves a wide range of applications with diverse requirements in terms of policy constraints. The diverse requirements of these applications are not well served by the existing Internet routing architecture. What is needed is an architecture that makes use of a set of paths between each source and destination that support the full range of policies available in a network.

(10) This disclosure provides a solution to the problems of congestion and providing policy-control of the use of network resources for network applications and administrators through the routing of traffic over multiple paths between a given source and destination. An example of this policy control relating to the use of a network in a military context where paths are rated as to the level of sensitivity of content they can carry (e.g. TOP-SECRET, SECRET, UNCLASSIFIED). One path that traverses links that provide a high level of security (e.g. fiber optic links, which are difficult to tap, in secured facilities, wireless links using strong encryption protocols where the end-points are in secured facilities, etc.) would be rated to carry TOP-SECRET traffic, while another path composed only of relatively unsecured links (e.g. a path over the public Internet) would be rated to only carry UNCLASSIFIED traffic. In the abstract these paths are not comparable. However, in the context of a specific use, one will generally be clearly preferred over the other (e.g. sensitive military operational traffic would require the TOP-SECRET path while general web browsing could make use of the UNCLASSIFIED path).

(11) These constraints can be defined using a Boolean Algebra where Boolean variables are used to represent policy-relevant properties of network traffic and network state, and Boolean expressions composed of these variables express the policy constraints required of flows using the network.

(12) The techniques use a Boolean algebra to define and compute the set of paths in a network that satisfy constraints defined using the Boolean algebra. U.S. Pat. No. 9,197,544, which is incorporated herein by reference, discusses the use of a path algebra in the context of dominant path routing instead of a Boolean algebra for Boolean constrained routing.

(13) A Boolean algebra can be used in a “General-Policy-Based Dijkstra” algorithm to compute the set of paths that simultaneously provide the full range of policies (in terms of the Boolean constraints) available in the network.

(14) This disclosure provides for the computation of routes subject to Boolean constraints expressing policies, and the use of these paths subject to congestion reduction. This disclosure also provides a forwarding technique based on the routing.

(15) A flow is defined as a sequence of packets that satisfy the same set of constraints (either Boolean only or both Boolean and performance) and are therefore subject to the same set of policies. The term flow in the present context is not related to IPv6, and, actually, is independent of any specific protocol.

(16) One path value (x) is said to dominate another (y) where the set of truth assignments where y is true is a subset of the truth assignments where x is true (in their truth tables). So the Boolean expression x satisfies more truth assignments than y. For a network example, if we have a shorter path A with path value Boolean expression y and a longer path B with Boolean expression x, we are going to want to include route B in our routing tables because, even though it is longer, if it satisfies some potential truth assignments that the shorter route A does not satisfy.

(17) In the dominant set multipath routing (DSMR) patent (U.S. Pat. No. 9,197,544) dominance in DSMR is defined differently, as follows: “The full range of performance is defined by a set of dominant routes, where each route from the source node to the destination node in the data network has multiple distinct performance metrics defining coordinates of a corresponding point in a multi-dimensional space. The multiple distinct performance metrics defining coordinates of the multi-dimensional space may include, for example, metrics such as a bandwidth metric, a latency metric, a jitter metric, and a reliability metric. Each of the dominant routes is defined as a route that has a corresponding point in the multi-dimensional space that is maximal with respect to a partial order defined on points in the multi-dimensional space corresponding to routes from the source node to the destination node.”

(18) For BCMR dominance is defined very differently. A Boolean expression can be described using a truth table with one column for each Boolean variable in the expression, and a final column for the Boolean expression. Each row contains a truth assignment of the values of either True or False to each variable (so, for n variables there will be 2.sup.n rows), and the expression column shows the value of the expression given the truth assignments to the variables in that row.

(19) FIG. 6 is an outline of the steps of a method for packet routing according to one embodiment of the invention. In step 600 the network equipment computes, for each source node in the data network and each destination node in the data network, a set of multiple routes providing a full range of performance from the source node to the destination node. The details of this step will be described in more detail below. In step 602, the network equipment selects, for a packet (or flow) originating from a source node and addressed to a destination node, a route selected from the set of multiple routes computed in step 600. The path selection may be implemented, for example, using an oracle that always assigns flows to paths that both satisfy the flow's QoS requirements and have adequate available bandwidth for the new flow. In step 604, the network equipment forwards the packet in accordance with the route selected in step 602.

(20) FIG. 7 is a schematic diagram illustrating a portion of a network including multiple router devices 1002-1016 and a central network controller device 1000, according to one embodiment of the invention. The dashed lines indicate two alternate routes between device 1006 and device 1014. One route, indicated by a short dashed line, passes through intermediate devices 1002 and 1016. Another route, indicated by a long dashed line, passes through intermediate devices 1004 and 1002. These two routes might, for example, represent the multiple routes providing a full range of policies from source node 1006 to destination node 1014.

(21) The router devices 1002-1016 may be conventional routers with standard forwarding technologies integrated into these routers and their software, modified to implement the techniques of the present invention. In some embodiments, the computing of the multiple paths, the selecting of a route, and the forwarding steps are all performed by each of the router devices 1002-1016. In these embodiments, the central controller 1000 is not necessary and may be eliminated. In other embodiments, compatible with “Open Flow” approaches to routing, the central controller 1000 computes the multiple routes. This precomputed routing information is then transmitted to each router device. For example, controller 1000 may compute the multiple routes from router 1006 to router 1014, then remotely updates the forwarding states of routers as appropriate. Each router with a packet to forward then independently selects a route from the multiple routes and forwards the packet over the selected route. This embodiment might be particularly useful in the case of a small or medium internet service provider (ISP), or organizations such as universities or larger corporations. In yet another embodiment, the central controller node 1000 not only computes the multiple routes, but also selects routes. For example, a router 1006 may query the central controller 1000 as needed to determine a route to forward a packet over. The central controller 1000 selects a route from the multiple routes and informs the router of the selection as a response to the query. In this embodiment, it is not necessary for central network controller to transmit computed multiple route forwarding information to the router devices. Allowing the central controller to select routes allows more intelligent congestion control in the network, but may increase latency.

(22) We now discuss an algorithm, according to one embodiment of the invention, for computing a set of routes in a network that provide a full range of performance from a source node to a destination node. This algorithm is preferably precomputed, i.e., in advance of any particular packet or flow being transmitted onto the network rather than computed on-demand with each new packet or flow.

(23) The routing algorithm is based on the data structure model shown in FIG. 5. In this structure, a balanced tree 500 (Bi) is maintained for each node in the graph to hold newly discovered, temporary labeled routes for that node. The heap 502 T contains the lightest weight entry from each non-empty Bi (for a maximum of n entries). A queue 504 Pi is maintained for each node which contains the set of permanently labeled routes discovered by the algorithm, in the order in which they are discovered (which will be in increasing weight).

(24) After multiple routes are computed, they are used for routing flows. For a given flow having a policy constraint specified by a Boolean expression, a route is selected from the set of multiple routes such that the route satisfies the policy constraints for the flow. The packets of the flow are forwarded in accordance with the selected route. Performing traffic classification at each hop in the network would be prohibitively expensive. To avoid this, preferred embodiments use label-swap forwarding so that only the first router that handles a packet needs to perform a traffic classification before forwarding it. Accordingly, the forwarding state of a router is enhanced to include local and next hop forwarding label information, in addition to the destination and next hop information existing in traditional forwarding tables, as shown in the table for node W. Traffic classifiers are placed at the edge of an internet, where “edge” is defined to be any point from which traffic can be injected into the internet. FIG. 8 illustrates schematically aspects of packet processing by a router device 800 connected to an internet subnet 802 according to one embodiment of the invention. The packet processing includes checking if a packet is labelled 804. If it is not, applying a traffic classifier 806. Then, label-swap forwarding 808 is applied and if the packet is not local, it is forwarded back onto the subnet 802. A routing process 812 informs the label-swap forwarding 808 and traffic classifier 806.

(25) To date, label-swapping has been used in the context of connection-oriented (virtual circuit) packet forwarding architectures. In these applications, a connection setup phase establishes the labels that routers should use to forward packets carrying such labels, and a label refers to an active source-destination connection. Also known is the technique of threaded indices, in which neighboring routers share labels corresponding to indexes into their routing tables for routing-table entries for destinations, and such labels are included in packet headers to allow rapid forwarding-table lookups. The forwarding labels according to embodiments of the present invention are similar in some aspects to threaded indices. A label is assigned to each routing-table entry, and each routing-table entry corresponds to a policy-based route maintained for a given destination. Consequently, for each destination, a router exchanges one or multiple labels with its neighbors. Each label assigned to a destination corresponds to the set of service classes satisfied by the route identified by the label.

(26) The forwarding architecture according to embodiments of the present invention may be implemented, for example, using the downstream tag allocation method described in Cisco's Tag Switching Architecture. In downstream tag allocation, routers allocate tags as a part of the routing computation, assigning a tag to each forwarding table entry. The binding of these tags with routes is then advertised to adjacent routers that support tag switching. Routers can use the tag information to construct their own Tag Information Base, which is used for label-swap forwarding.

(27) In addition to BCMR being implemented with labels, it can be implemented with source routing in general, and segment routing in particular. In some embodiments, selecting the route may include, if a source route is not present in the packet, computing the source route from traffic classification rules specified in terms of contents of the packet, in terms of a user associated with the packet, in terms of a port the packet arrives on, or in terms of one or more other environmental factors. If a source route is already present in the packet, the forwarding may include forwarding the packet based on the source route in the packet.

(28) In some embodiments, selecting the route may include, if a segment list is not present in the packet, computing the segment list from traffic classification rules specified in terms of contents of the packet, in terms of a user associated with the packet, in terms of a port the packet arrives on, or in terms of one or more other environmental factors. If a segment list is already present in the packet, the forwarding may include forwarding the packet based on the segment list in the packet.

(29) We now discuss in more detail the Boolean Constrained Multipath Routing (BCMR) algorithms. Table 1 defines the notation used in these algorithms, and Table 2 defines the primitive operations for queues, heaps, and balanced trees used in the algorithms, and gives their time complexity used in their complexity analysis. Algorithm 1 is a listing of a modified Dijkstra algorithm that computes the set of shortest routes to each destination that satisfies all truth assignments for the Boolean algebra available from a path in the network. Algorithm 2 extends the BCMR algorithm to compute the maximal set of routes for each satisfiable truth assignment in the network.

(30) The SAT(φ) primitive of the traffic algebra is the satisfiability problem of traditional Boolean algebra. SAT answers the question “is there an assignment of truth values to the propositional variables in φ such that φ evaluates to true?” The SAT(φ) primitive evaluates to 1 (true) if such a truth assignment exists, and 0 (false) otherwise. Satisfiability must be tested in two situations by the algorithms presented below. First, when a new route to a destination is considered for comparison to an existing route for the same destination (e.g. lines 5 and 13 in Algorithm 1), they should only be compared if classes of traffic exist that can use either route. Therefore, new routes are only compared with existing routes when the conjunction of their path predicates is satisfiable. Second, given that classes of traffic exist that can use either path, the algorithms must determine whether all traffic supported by one path could use the other. This is the case if the path predicate for one path implies (“.fwdarw.”) the other or, more precisely, if the expression (ε.sub.x.fwdarw.ε.sub.y) is always true (i.e. is valid). Determining if an expression is valid is equivalent to determining if the negation of the expression is unsatisfiable. Therefore the expressions at lines 10 and 13, of the form ε.sub.1.fwdarw.ε.sub.2 are equivalent to ¬SAT(¬(ε.sub.1.fwdarw.ε.sub.2)) (or ¬SAT(ε.sub.1∧ε.sub.2)). The satisfiability decision performed by SAT(ε) is the prototypical NP-complete problem. As is typical with NP-complete problems, it has many restricted versions that are computable in polynomial time.

(31) In the DSMR elements of Algorithm 2, path weights are composed of multi-component metrics that capture all important performance measures of a link such as delay, delay variance (“jitter”), available bandwidth, etc. The best set of paths to a destination is defined using an enhanced version of the path algebra defined by Sobrinho (IEEE/ACM Transactions on Networking, 10(4):541-550, August 2002).

(32) Formally, the path algebra P=<W, ⊕, , .Math., θ, ∞> is defined as a set of weights W, with a binary operator ⊕, and two order relations, and defined on W. There are two distinguished weights in W, 0 and ∞, representing the least and absorptive elements of W, respectively. Operator ⊕ is the original path composition operator, and relation is the original total ordering of Sobrinho, which is used to order the paths for traversal by the path selection algorithm. Operator ⊕ is used to compute path weights from link weights. The routing algorithm uses relation to build the forwarding set, starting with the minimal element, and by the forwarding process to select the minimal element of the forwarding set whose parameters satisfy a given QoS request. A new relation on routes, .Math., is added to the algebra and used to define classes of comparable routes and select maximal elements of these classes for inclusion in the set of forwarding entries for a given destination. Relation .Math. is a partial ordering (reflexive, anti-symmetric, and transitive) with the following, additional property:
Property 1(ω.sub.x.Math.ω.sub.y).Math.(ω.sub.xω.sub.y).

(33) An example path algebra based on weights composed of delay and bottleneck bandwidth is as follows:
ω.sub.i≡(d.sub.i,b.sub.i)
0≡(0,∞)
∞≡(∞,0)
ω.sub.i⊕ω.sub.j≡(d.sub.i+d.sub.i,Min(b.sub.i,b.sub.j))
ω.sub.iω.sub.j≡(d.sub.i<d.sub.j)∨((d.sub.i=(d.sub.j) ∧(b.sub.i≤b.sub.j))
ω.sub.i.Math.ω.sub.j≡(d.sub.j≤d.sub.i)∧(b.sub.j≥b.sub.i)

(34) TABLE-US-00001 TABLE 1 Notation. A(i) ≡ Set of edges adjacent to i in the graph. ω.sub.ij ≡ Weight of edge (i, j). ε.sub.ij ≡ Link predicate of edge (i, j). P ≡ Queue of permanent routes to all nodes. P.sub.n ≡ Queue of permanent routes to node n. T ≡ Heap of temporary routes. T.sub.n ≡ Entry in T for node n. B.sub.n ≡ Balanced tree of routes for node n. E.sub.n ≡ Summary of traffic expression for all routes in P.sub.n.

(35) TABLE-US-00002 TABLE 2 Operations on Data Structures. Queue Push(r, Q) Insert record r at tail of queue Q Head(Q) Return record at head of queue Q Pop(Q) Delete record at head of queue Q PopT ail(Q) Delete record at tail of queue Q d-Heap Insert(r, H) Insert record r in heap H IncreaseKey(r, r.sub.h) Replace record r.sub.h in heap with record r having greater key value DecreaseKey(r, r.sub.h) Replace record r.sub.h in heap with record r having lesser key value Min(H) Return record in heap H with smallest key value DeleteMin(H) Delete record in heap H with smallest key value Delete(r.sub.h) Delete record r.sub.h from heap Balanced Tree Insert(r, B) Insert record r in tree B Min(B) Return record in tree B with smallest key value DeleteMin(B) Delete record in tree B with smallest key value

(36) TABLE-US-00003 Algorithm 1: Modified Dijkstra SPF algorithm for BCMR. algorithm BCMR begin Push(<s,s,0,1>, Ps); for each {(s, j ) ∈ A(s)}  Insert(<j,s,ω.sub.sj,ε.sub.sj >, T); while(|T| >0)  begin  >i,p.sub.i,ω.sub.i,ε.sub.i > ← Min(T);  DeleteMin(B.sub.i);  if(|B.sub.i| = 0)   then DeleteMin(T )   else IncreaseKey(Min(B.sub.i), T.sub.i);  if (¬ (ε.sub.i .fwdarw. E.sub.i))   then begin    Push(<i,p.sub.i,ω.sub.i,ε.sub.i >, P.sub.i);    E.sub.i ←Ei∨εi;    for each {(i,j) ∈ A(i) | SAT(ε.sub.i ∧ε.sub.ij) ∧ ¬((ε.sub.i ∧ε.sub.ij) .fwdarw. E.sub.j)}     begin     ω.sub.j ←ω.sub.i + ω.sub.ij;ε.sub.j ←ε.sub.i ∧ε.sub.ij;     if (Tj = ø)      then Insert(<j,i,ω.sub.j,ε.sub.j >, T)     else if (ω.sub.j < T.sub.j.ω)      then DecreaseKey(<j,i,ω.sub.j,ε.sub.j >, T);     Insert(<j,i,ω.sub.j,ε.sub.j >, B.sub.j);     end    end  end end

(37) TABLE-US-00004 Algorithm 2: Modified Dijkstra SPF algorithm for combined DSMR & BCMR. algorithm Combined DSMR & BCMR begin Push(<s,s,0,1>, P.sub.s); for each {(s, j ) ∈ A(s)}  Insert(<j,s,ω.sub.sj,ε.sub.sj >, T); while(|T| >0)  begin  <i,p.sub.i,ω.sub.i,ε.sub.i > ← Min(T);  DeleteMin(B.sub.i);  if(|B.sub.i| = 0)   then DeleteMin(T )   else IncreaseKey(Min(B.sub.i), T.sub.i);  ε.sub.tmp ← ε.sub.i; ptr ← Tail(P.sub.i);  while ((ε.sub.tmp/= 0) ∧ (ptr/= ø))   if (wi ⊏ ptr.ω)    ε.sub.tmp ← ε.sub.tmp ∧ ¬ptr.ε; ptr ← ptr.next;  if(ε.sub.tmp ≠0)   then begin    Push(<i,p.sub.i,ω.sub.i,ε.sub.i > P.sub.i);    for each{(i,j) ∈ A(i) | SAT(ε.sub.tmp Λε.sub.ij)}     begin     ω.sub.j ←ω.sub.i ⊕ω.sub.ij;ε.sub.j ←ε.sub.tmpΛεi.sub.j;     if (T.sub.j = ø)      then Insert(<j,i,ω.sub.j,ε.sub.j >, T)     else if (ω.sub.j < T.sub.j.ω)      then DecreaseKey(<j,i,ω.sub.j,ε.sub.j >, T);     Insert(<j,i,ω.sub.j,ε.sub.j >, B.sub.j);     end    end  end end

(38) Dijkstra is not needed but just an example of a method that could be used to reach all nodes. Others include Bellman Ford and any other shortest path routing algorithms. Need not be limited to shortest path first specifically, but those work.

(39) In the graph shown in FIG. 1 paths (1,2,3,4) and (1,5,4) have Boolean constraint “a and b” with truth table shown in FIG. 2A, while path (1,6,4) has constraint “a or b” with truth table shown in FIG. 2B.

(40) Given these paths the combined DSMR and BCMR routing algorithm would compute the routing table entries from node 1 to node 4 (where the weights are (bandwidth, delay) shown in FIG. 3 and the path algebra is Shortest-Widest.

(41) In this table the list in the Boolean Constraint column is a shorthand version of the truth tables shown above. Specifically ‘F’ and ‘T’ represent False and True, and each entry in the list represents the corresponding entry in the table (so the first entry in the list is the value for a=False and b=False, the second entry is for a=False and b=True, etc.). These entries are to be interpreted in terms of a (logically) distinct table for each truth assignment to the variables used in the constraints. This interpretation can be visualized as shown in FIG. 4.

(42) As an example, a flow with the constraint “not a and b” (and thus the truth table [T,T,F,T]) can use routes for any of the satisfying truth assignments of a and b; i.e. for the truth assignments evaluating to True in the flow constraints truth tables, or [a=F, b=F], [F,T], [T,T]. Entries in the Routes column are in the format “(bandwidth, delay) next hop”. Translating this to usable routes, this flow can use any of the available paths. Concretely, the entry for [a=F, b=F] is empty (‘—’), for [F,T] is “(5,8) 6”, and for [T,T] is “(10,5) 2, (7,4) 5” for the following list of usable routes:

(43) (10,5) 2, (7,4) 5, (5,8) 6

(44) However, given there are 2.sup.n rows in such a truth assignment table (i.e. 2 routing tables to search for a given flow constraint), where n is the number of constraint variables, this approach to forwarding table lookups is prohibitively expensive. Fortunately an alternative solution is suggested by the observation that the set of usable routes for a given flow are those where the performance constraint is satisfied, and both the routing table constraint and the flow constraint evaluate to True. This is exactly the set of routing table entries where the performance constraint is satisfied (i.e. if RT.sub.pc is the routing table performance constraint ad F.sub.pc is the flow performance constraint, the entries where “F.sub.pc.Math.RT.sub.pc”), and the conjunction of the routing table constraint and the flow constraint is satisfiable; i.e., if RT.sub.bc is the routing table constraint (“Boolean Constraint” in the routing table above) and F.sub.bc is the flow performance constraint (the truth table [T,T,F,T] representing the constraint “not a and b” above), the set of usable routes are those where SAT(“RT.sub.bc and Fbc”) (SAT( ) is the standard Boolean Satisfiability function) is True.

(45) This is concisely described in the following pseudo-code (where R.sub.d is the set of routes computed for destination d containing routes of the form <dest, next hop, forwarding information, performance constraint, Boolean constraint>; forwarding information is the information used to forward the traffic, such as label swap information):

(46) TABLE-US-00005 algorithm ForwardingSet( R.sub.d, F.sub.pc, F.sub.bc ) begin FS ← { }; // The computed forwarding set. for each { <d,nh,fi,pc,bc> ∈ R.sub.d }  if ( F.sub.pc ⊏ RT.sub.pc and SAT( RT.sub.bc and F.sub.bc))   then Append ( <d, nh, fi>, FS ) return ( FS) end

(47) This algorithm provides an efficient, single pass solution for identifying candidate paths for the flow. The returned set of routes are those that satisfy the constraints; one of these can be selected based on other criteria, such as minimal congestion for use by the given flow.