Adaptive routing system and method for Qos packet networks

<b>Field Of The Invention</b>

The present invention relates to packet networks, and, more particularly, to adaptive routing of packets in a communications network based on quality of service provisioning.

<b>Description Of The Related Art</b>

Packet network service providers, such as those providing Internet Protocol (IP) networks, are presently developing and providing differentiated services. In particular, service providers are interested in differentiated services as part of provisioning and maintaining networks for customers with a variety of voice and data needs. For example, virtual private networks (VPNs) allow service providers to establish and tear-down connections for a large number of users, while billing only one customer or client (e.g., a large corporation or government agency) for the service. However, the customer or client may require a certain amount of guaranteed bandwidth, minimum transport delay, or other metric for some or all of the data transported through the VPN. Service providers generally desire a higher revenue for data transported through the VPN when a customer demands such differentiated services.

In the art, the term "physical path" denotes the path between source and destination pairs for a given communication stream of data, or packet flow, together with intermediate nodes, if any, and the physical links that connect the nodes. In networks of practical size and complexity, many sets of multiple physical paths may exist, each provisioned to carry one or more corresponding packet flows. The network operator may specify a predetermined bandwidth for the corresponding stream or packet flow along each link of the possible physical paths. The specified bandwidth may equal the full bandwidth, or some quantity less than the full bandwidth, or no bandwidth at all. Although a physical path may exist between a source and destination pair, the full bandwidth of the physical path links may be unavailable for the corresponding packet flow.

In addition, the term "logical path" (also called a "virtual path") denotes a path between a given source and destination pair as defined by connection metrics, such as delay or bandwidth. Logical (virtual) paths are not determined purely by physical considerations, but instead are partly defined by parameters that may be specified and/or changed. Individual virtual paths may require less than the fully assigned bandwidth physically available on the physical links that the paths occupy. Thus, several virtual paths may co-exist along part or all of a physical path, allowing each physical link of the network to simultaneously support several virtual paths.

Packet networks that provide differentiated services generally include a routing method that allows the network to determine a logical path through the network from a given source to a given destination. The routing method may be part of a process performed in each router of the network. Each router may learn the network topology by exchanging link and router information between directly connected routers. Once the router determines the network topology, the router may employ a path-selection process that determines the logical path through a network between the source and destination pair over the physical links according to predefined connection metrics. Each router determines the same logical path through the packet network given the same information. Packets received by each router are then routed along the determined path.

A standard protocol employed by IP networks to determine network topology and link routing is the Open Shortest Path First (OSPF) protocol, as outlined in J. Moy, "OSPF Version 2," Internet Draft, Request for Comment (RFC) 2178, July 1997. The OSPF protocol employs the destination (i.e., shortest path to destination) as the metric for the path-selection process. However, with destination as the only metric, only a "best effort" is employed to route packet flows. Best effort implies that, while the packets are re-routed, no other QoS provisioning commitment, such as minimum bandwidth, delay or loss, applies to the packet flow. Routers of the prior art may route packets based on other factors, such as available bandwidth. However, when the OSPF protocol is employed as the routing method, distribution of packet flows over the links is based on shortest path and not provisioned QoS commitments.

Routing methods may determine logical paths and allocate corresponding bandwidth to the links in the network, with such allocation according to the source and destination pair, subnetwork, and class of service. This path-selection method or determination may be referred to as logical network design. One important element of logical network design is selection of a set of physical paths through the network having sufficient capacity for carrying the estimated traffic of a communication stream or packet flow The routing method may base the determination on such factors as the network topology, the currently available buffer space at the nodes, and the currently available link capacities.

Significantly, the network operator may have QoS commitments with its customers, such as guaranteed bandwidth or maximum cell-loss probability. The path-selection process may account for such commitments, but the routing method may require simplifications to characterize variable traffic characteristics in a form that the routing method can use for logical path determination. For example, certain networks, particularly high-speed networks, may support the networking protocol known as asynchronous transfer mode (ATM). Such high-speed networks typically carry multiple services having different traffic characteristics, including both constant bit rate traffic and variable bit rate traffic. An important simplification for routing methods considering variable bit rate traffic in networks, such as ATM networks, is provided by the concept of "effective bandwidth."

Effective bandwidth of a packet flow defines the bandwidth of the packet flow in terms of the node buffer size and the average and peak rates of the packet flow, assuming the node operates with a leaky bucket regulator. An effective bandwidth may be determined for each packet flow, of a network where the packet flows are multiplexable, the total effective bandwidth of all packet flows is less than or equal to the total network capacity, and the packet flows exhibit loss-less performance. (i.e., the packet flows may be rearranged over multiple physical paths while maintaining desired delay or bandwidth for each packet flow). For networks having both multiplexable and non-muliplexable packet flows, the two types of traffic may be separately analyzed, with portions of the total network capacity allocated to each traffic type.

Effective bandwidth, and allocation of bandwidth and buffer capacity based on effective bandwidth, is described in detail in A. Elwalid et al., "A New Approach For Allocating Buffers and Bandwidth to Heterogeneous, Regulated Traffic in an ATM Node," <u>IEEE Journal on Selected Areas in Communications</u>, Vol. 13, No. 6, (August 1995) 1115-1127 (incorporated herein by reference and referred to as "Elwalid et al."). A routing algorithm that accounts for variable bit rate traffic in ATM networks with effective bandwidth, is described in detail in U.S. Patent No. 5,838,663, issued on November 11, 1998 entitled "A Method for Admission Control and Routing by Allocating Network Resources in Network Nodes", which is incorporated herein by reference.

Once logical paths are specified, the routers of the network generally must support at least two types of messages for the packet flows and network administration: data messages and control messages. Data messages are packets containing user information transported between the source and destination pair. Control messages are messages interpreted by network elements, such as the routers, to administer connections and exchange network information. These control messages may be employed to ensure that the packets are interpreted and routed in a manner that provides the desired commitment of the path-selection process. Control messages may be included in packet headers, or may be separate and distinct packets.

One approach of the prior art for providing differentiated services employs type-of-service (TOS) bits defined in the packet header, or TOS addressed metrics in the packet payload. The TOS bits are interpreted by routers within the network in an agreed upon manner so that each network node provides the desired QoS commitments of the service when routing the packet flow. This approach may allow for distribution of each and all resource requests to all nodes of the network. Alternate approaches may be reservation-based and may employ signaling to reserve network resources for the duration of a packet flow, or packet flow aggregates. A protocol to signal reservation of network resources in a network is the Reservation Setup Protocol (RSVP). RSVP, as an example, may be used in conjunction with service models, such as guaranteed rate and controlled load service models, to request the desired QoS commitments for certain flows.

Once the connection is established, the router includes a routing fabric to physically route packets received at input ports to specific output ports for transport to the next node or destination. Packet filters may be employed with the routing fabric to determine actions to be taken for packets having certain source and destination addresses arriving at the router. Actions may be that routing of packets sent from one or more of specified sources is denied (e.g., actions for "firewall" or security purposes), or that a specific action is to be taken for that packet having a specified source address (e.g., actions for routing to a specific, alternate destination). The router may be provided with a table or list of filter rules specifying the desired actions for corresponding field addresses. The packet filter allows the router to associate fields of received packets with the table or list entries.

Packets comprise, for example, a header and a payload that may include user data. A header of the packet includes fields or parameters, such as a source address where the data originates and at least one destination address where the data is to be routed. Mother parameter in the header may be a protocol type identifying a particular protocol employed in the communication network. Source and destination addresses may be logical addresses of end hosts. The header may also include, for example, certain types of flags in accordance with protocol type, such as TCP, depending upon the receiver or transmitter application.

The IP packet header fields typically contain up to 128 bits of parameter information, including source and destination addresses, physical source and destination port numbers, interface number, protocol type, etc. Filter rules may also specify, for example, that for received packets with fields in the header specifying a particular destination address, the packet should or should not be forwarded through specific output links or output ports. Thus, a variety of filter rules may be implemented based on packet field information. For example, such filter rules might be based on 1) source addresses; 2) destination addresses; 3) source ports; 4) destination ports; and/or 5) any combination of these fields. Consequently, such packet filtering may be employed by layer four switching applications.

Each of the fields or parameters in the header may be represented as points along an axis of a dimension. The general packet classification problem of a packet filter may then be modeled as a point-location in a multi-dimensional space. One or more field values of the packet define a point in the multi-dimensional space. A packet filter rule associated with a range of values in each dimension defines an object in the multidimensional space.

A point-location algorithm in a multi-dimensional space with multi-dimensional objects finds the object that a particular point belongs to. Given a received point <i>EP</i> = <i>{E</i>_<i>1</i><i>, E</i>_<i>2</i><i>, . . E</i>_<i>D</i><i>}</i> in a space having D dimensions, the point-location algorithm finds one or more of a set of <i>n</i> D-dimensional objects including the point <i>EP</i> (<i>n</i> being an integer greater then 0). The general case of D &gt; 3 dimensions may be considered for the problem of packet classification. For the special case of two dimensions, the filter rules defined for field ranges are modeled as objects in two dimensions, forming rectangles in the 2-dimensional space. The specific case of filter rules defined for field ranges that are modeled as objects in two dimensions may correspond to switching of packets through a routing fabric based on source address/port and destination address/port.

Once the physical and logical paths through the network are determined, network resources are reserved through the nodes of the network when a link is established and packet flows between source and destination pairs begin. However, when a link is broken, such as by a disconnected T1, T3, or fiber-optic connection to an interface card of the network node, or when a node fails, such as when a router fails, the routing mechanism must determine alternate paths through the network to re-establish the packet flows.

Since packet network links are generally in a state of flux, service providers may not be able to effectively provide QoS provisioning, and hence receive revenue, when re-routing does not effectively preserve the QoS commitments to the VPN. Routing mechanisms of the prior art currently route packets through the network based on destination address. Reservation-based protocols alone may only request bandwidth for a link to be established, with no guarantee of success of the request.

<b>Summary Of The Invention</b>

The present invention relates to adaptive routing, and more particularly to generating new routing paths through a router of a packet network. Generating new routing paths may occur when new paths for packet flows are desired because a trigger event, such as a node/link failure or a network topology/provisioning change, occurred in the packet network. In accordance with the present invention, 1) network topology information and 2) quality of service (QoS) provisioning information are collected for each packet flow through one or more routers of the packet network. A path for each packet flow is determined using a general routing optimization method, such as a multicommodity flow routing method, based on the QoS provisioning and network topology information. A set of one or more filter rules is generated for the router based on the one or more paths for the one or more packet flows passing through the router, each filter rule defining a physical path for one or more packet flows through the router. A selected filter rule is applied to each packet of a packet flow to cause each packet to traverse the corresponding path through the router.

The present invention may allow for adaptive routing using packet classification with filter rules. New path routing may be generated as provisioning entries generated by a multicommodity flow-based routing method using network topology information and quality of service (QoS) provisioning information. The provisioning entries may then be translated into filter rules of a packet classifier that implements the new routing paths, thereby implementing adaptive routing in accordance with the present invention.

<b>Brief Description Of The Drawings</b>

Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which: <ul id="ul0001" list-style="none"><li>FIG. 1 shows block diagram of a packet network employing adaptive routing in accordance with the present invention;</li><li>FIG. 2 shows a block diagram of an exemplary processing section of a router implementing adaptive routing in accordance with the present invention;</li><li>FIG. 3 is an exemplary flowchart for a router implementing adaptive routing in accordance with the present invention when a trigger event is detected;</li><li>FIG. 4 shows an exemplary implementation of a packet filter of a packet classifier as shown in FIG. 2;</li><li>FIG. 5 shows a block diagram of an exemplary distributed processing and database (DPD) system as may be employed with the present invention;</li><li>FIG. 6 shows an exemplary line format of an OSPF packet showing the position of the type of service bits;</li><li>FIG. 7 shows an exemplary line format of an advertisement packet based on an OSPF packet that may be employed with the present invention;</li><li>FIG. 8 shows a flowchart of a path-selection process that may be employed by the QoS routing module of FIG. 4;</li><li>FIG. 9 shows an illustration of packet filtering for two fields of a packet header corresponding to a point location in 2-dimensions;</li><li>FIG. 10 shows an exemplary flowchart for the general routing optimization as may be employed by the present invention; and</li><li>FIG. 11 shows a flowchart for the step of determining route loss probabilities and network sensitivities of the method shown in FIG. 10 with stochastic variables.</li></ul>

<b>Detailed Description</b>

FIG. 1 shows block diagram of a packet network <b>100</b> employing adaptive routing in accordance with the present invention. The packet network <b>100</b> includes network routers <b>102-107</b>, and a network management station <b>108</b>. For convenience of the following described embodiments, the routers are defined as a source router <b>102</b> in communication over a link with destination routers <b>106</b> and <b>107</b> through intermediate routers <b>103, 104</b> and <b>105</b>. The data path established through links between the source router <b>102</b> and destination routers <b>106</b> and <b>107</b> may be employed to transfer information, or communication streams of data, by packet sequences defined as packet flows. Each packet of the packet sequences may have a header including a source address, source port range, destination address, and destination port range.

Each of the routers <b>102-107</b> may typically support an Internet Protocol (IP), for example, and provide for Quality of Service (QoS) provisioning for links of the network. These routers are interconnected by links, which are physical transport media such as T1s, T3s, or optical fiber (e.g., SONET links such as OC1, OC3). However, the present invention is not limited to these fixed or wired types of networks, and is not limited by link-layer characteristics. Each link has a capacity defined in terms of, for example, total available channels, bandwidth, bit-error rate and delay. Each link capacity provides a portion of total available capacity of packet network <b>100</b>.

Network management station (NMS) <b>108</b> (e.g., a central provisioning station for a virtual private network (VPN)) allows network administrators to remotely allocate transmission capacity of routers and links between a source and a destination pair (source-destination pair) within the network. A given VPN may comprise many source-destination pairs. For such purposes, the NMS <b>108</b> maintains a network management database <b>109</b> of addresses corresponding to the source-destination pairs, and a pair is also identified by the address fields in the header of a network packet. Central provisioning of packet network <b>100</b> also includes QoS provisioning, and so each source-destination pair is assigned specified QoS commitments for packet flows corresponding to the source-destination pair.

The source-destination pair defines point-to-point traffic through the packet network <b>100</b>, where "point" refers to the ingress (source) or egress (destination) network element. For networks following the OSPF protocol, the point may typically be a border router for transit traffic. Source router <b>102</b> is shown as an ingress point from external network N₁, while the destination routers <b>106</b> and <b>107</b> are shown as egress points to networks N₂ and N₃, respectively.

For packet network <b>100</b>, packet flows may be classified by header information, and grouped into classes, super-classes, or groups of super-classes according to source address ranges and destination address ranges. Classes may be associated with packet flows with common QoS commitments. Super-classes, or groups of super-classes may be associated with virtual private networks (VPNs). Desirably, ranges of source and destination addresses are contiguous for each class, super-class, or groups of super-classes. The packet network <b>100</b> may employ a message of a protocol to request resources. Such message may be, for example, Type of Service (TOS) bits of the OSPF protocol in the packet header, TOS addressed metrics of the packet payload, or the control messages of the RSVP protocol. Such resource requests may allocate bandwidth for packet flows from the source <b>102</b> to one or more of the destinations <b>106</b> and <b>107</b> through the network routers <b>103</b>, <b>104</b>, and <b>105</b>.

QoS provisioning specifies certain minimum allowed characteristics of the transmission capacity of the network to be assigned to provisioned packet flows between source-destination pairs. Transmission capacity may be directly related to the capacity of the links in the network, and such characteristics for the packet flows may be bandwidth, delay, and loss (i.e., probability of a lost packet). Such characteristics may be related through available buffers of the router. The QoS provisioning associated with addresses of each source-destination pair is also maintained in the network management database <b>109</b>. QoS provisioning may also include associated revenue and cost corresponding to each QoS provisioning characteristic, which revenue and cost may be related to revenue paid to service providers by clients based on minimum levels of QoS characteristics provided to packet flows and the cost of providing network connectivity, respectively.

Table 1 shows an exemplary provisioning table for QoS link provisioning of a packet flow as employed by a router in accordance with the present invention. <tables id="tabl0001" num="0001"><img file="EP1035751A2_D0001.tif" /></tables><tables id="tabl0002" num="0002"><img file="EP1035751A2_D0002.tif" /></tables>

As shown in Table 1, each packet flow may be identified with Class field, Revenue field values, and VPN-ID field, in addition to the typical provisioning information associated with the source-destination pairs through the routers of the network. The VPN-ID field value may be employed to associate the packet flow with a particular network client or virtual private network, and the Revenue field value is related a relative value of the packet flow to revenue generated for the network by the packet flow. The value for the Revenue field may not necessarily be a monetary quantity, but other network costs may be included (such as maintenance, lost capacity, connectivity costs, or provisioning costs). The QoS provisioning commitments may be associated with a class field value, and exemplary QoS provisioning commitments associated with a Class field are given in Table 2 for a router including a leaky bucket regulator. <tables id="tabl0003" num="0003"><table frame="all"><title>Table 2</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Field</entry><entry namest="col2" nameend="col2" align="center">Function</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="center">rate (<i>r</i>)</entry><entry namest="col2" nameend="col2" align="left">Average rate of the packet flow in bytes per second, or may be a token refresh rate for the leaky bucket regulator</entry></row><row><entry namest="col1" nameend="col1" align="center">bucket</entry><entry namest="col2" nameend="col2" align="left">Maximum number of packets that may be sent before a refresh of the bucket of the bucket regulator or depth</entry></row><row><entry namest="col1" nameend="col1" align="center">peak (<i>p</i>)</entry><entry namest="col2" nameend="col2" align="left">Maximum rate of the packet flow in bytes per second.</entry></row><row><entry namest="col1" nameend="col1" align="center">min</entry><entry namest="col2" nameend="col2" align="left">Minimum packet size, which may be employed to calculate a maximum or worst case expansion of traffic for a packet flow.</entry></row><row><entry namest="col1" nameend="col1" align="center">max</entry><entry namest="col2" nameend="col2" align="left">Maximum packet size, which may be employed to determine the number of bytes in the bucket.</entry></row><row><entry namest="col1" nameend="col1" align="center">delay</entry><entry namest="col2" nameend="col2" align="left">Maximum sustainable end-to-end delay in microseconds, which may be related to the maximum per hop delay, <i>dp</i> (if total maximum number of hops <i>n</i>_<i>max</i> is known.</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="center">lossreq</entry><entry namest="col2" nameend="col2" align="left">The maximum sustainable packet loss rate for which the packet flow may operate reliably.</entry></row></tbody></tgroup></table></tables>

The values for the fields shown in Table 2, such as rate, bucket, delay and loss of a leaky bucket regulator, may be related to the bandwidth available on specified links.

Each of the routers <b>102-107</b> comprises a processing section implementing the adaptive routing in accordance with the present invention. Other routers, not shown, that do not employ the adaptive routing in accordance with the present invention may exist in the network <b>100</b>. Each of the routers <b>102-107</b> is connected to at least one other router in the network <b>100</b>. The packet network <b>100</b> employs a standard protocol to determine and disseminate information regarding the connectivity of the links and routers within the network <b>100</b>, including information about link capacity and available bandwidth, for example. For the preferred embodiment of the present invention, this protocol for dispersion of link and router connectivity information (herein referred to "network topology information") may be provided from the corresponding function of the Open Shortest Path First (OSPF) protocol.

For the packet network <b>100</b>, each router maintains a database of network topology information. Consequently, each router knows 1) the existence of each other router in the network; 2) the connections between each router in the network, and 3) the identities of routers that interface to other packet networks "outside" of the packet network <b>100</b>. In the present context, "outside" may refer to packet networks N₁, N₂, and N₃ not supporting adaptive routing and/or part of a different service provider's network.

The Open Shortest Path First (OSPF) protocol commonly employed in IP networks includes a Shortest Path First (SPF) routing method for the path-selection process. For the preferred embodiments of the present invention, routers of network <b>100</b> employing adaptive routing in accordance with the present invention determine logical paths based on a multicommodity flow (MCF) routing method. The MCF routing method may employ information generated by SPF routing method of the OSPF protocol as initial provisioning values, and for provisioning values for non-real-time packet flows and for real-time, non-multiplexable packet flows. In addition, the routers connected in network <b>100</b> that do not employ adaptive routing in accordance with the present invention preferably employ a path-selection process based on the SPF routing method.

The MCF routing method accounts for the QoS provisioning assigned to source-destination pairs when routing packet flows. Packet flows may be comprised of several different sets of traffic for different users within a VPN. Before a link failure, a portion of the link's capacity is allocated to the source-destination pair. However, when the link fails, the different sets of traffic desirably have capacity of other links re-allocated to the sets of traffic. In addition, two possible classes of routing may be supported by adaptive routing: multi-path routing and single-path routing. Multi-path routing occurs when flows of a source-destination pair are split, with different ones of the sets of traffic allocated to different new paths, and hence links, through the network. Single path routing occurs when the entire group of sets of traffic are re-routed over the same new path.

If multipath routing exists in the packet network <b>100</b>, the multi-path routing may be decomposed into single path routing (i.e., multi-path from a source to N destinations, N an integer greater than 1, may be thought of as routing over N single paths. In addition, mathematical tools, such as Steiner path trees, heuristic bin packing, randomized routing, or shortest path spanning trees, may be employed by the algorithms described herein to reduce computational complexity resulting from decomposition of multi-path to single path routing. Consequently, the exemplary routing methods are described herein for single path routing. The present invention is not so limited, however, and one skilled in the art may extend the exemplary routing methods to multipath routing.

In addition, while the preferred embodiments of the present invention are described employing the OSPF protocol, other similar protocols that determine and disperse network topology information may be employed. Consequently, one skilled in the art may readily adapt the system and methods described herein to other such protocols and/or routing mechanisms. Similarly, while preferred embodiments are described that employ the SPF routing method as a path-selection process, other common routing methods may be employed and the present invention is not so limited

Referring to FIG. 1, each of the routers <b>102-107</b>, re-calculate new routing in accordance with similar path-selection processes based on similar QoS provisioning and similar network topology information. Consequently, each router desirably calculates the same routing and path selection for source-destination pairs.

However, under some network conditions, "loop packets" may exist (i.e., packets that repeatedly pass through the same sets of routers, rather than pass from the source to the destination.) Such network conditions may be, for example, when: 1) not all routers in the network employ the same routing protocol and the various routing protocols do not allow routers to be aware of each other; 2) the network topology or provisioning changes, resulting in a temporary mismatch of network topology information between routers; and 3) the network allows packets to be routed toward the source to find a router recognizing the desired source-destination pair. Loop packets may circulate between some network routers several times, causing unnecessary traffic congestion, as the loop packets "search" for a router that knows the complete path between the source and the destination route.

To reduce the number of loop packets that may be formed when the path-selection process is initiated, several techniques may be employed. A packet-hop counter limiting the number of hops (paths between routers) the packet traverses may be employed. New routing may be limited so that packets are only sent toward the destination. Signaling packets may also be employed between routers to identify and delete loop packets. For the exemplary embodiments described below, a method to reduce the number of loop packets such those described above is desirably employed in network <b>100.</b>

FIG. 2 shows a block diagram of an exemplary processing section of a router, e.g., router <b>105</b>, employing alternate path routing in accordance with the present invention. Processing section <b>200</b> includes a control processor <b>201</b>, routing processor <b>202</b>, packet classifier <b>203</b>, input link interface <b>204</b>, buffer section <b>205</b>, route allocation processor <b>206</b> and output link interface <b>207</b>. An implementation of the processing section and link interfaces of such router may be embodied in, for example, a Packet Star 6400 router, available from Lucent Technologies, Inc. of Murray Hill, New Jersey.

Packets of one or more packet flows are received at the input link interface <b>204</b> by the processing section <b>200</b>. Input link interface <b>204</b> may define one or more input ports, and may comprise the receive sections of one or more line termination cards that terminate at least one transmission line. The termination cards, such as T1, T3 or OC-3 termination cards, support one or more links through the bandwidth of each transmission line. Packets received from the input link interface are queued for processing in buffer section <b>205</b>, and may be concurrently provided to the packet classifier <b>203</b>. Buffer section may include buffers allocated to each input port. Packet classifier <b>203</b> contains one or more packet filters determining filter rules to be applied to each received packet. Based on the filter rules, route allocation processor <b>206</b>, which may simply be a crossbar switch, redirects the packet from the buffer section <b>205</b> to one or more corresponding output ports of the output link interface <b>207</b>. Output link interface <b>207</b> may define one or more output ports, and may comprise transmit sections of one or more line termination cards that terminate at least one transmission line.

The control processor <b>201</b> (or routing processor <b>202</b>) may include an element manager (not shown) that periodically reads statistics created from the header information of received packets. As shown in FIG. 2, signals may be exchanged between the packet classifier <b>203</b> and control processor <b>201</b> to collect or measure traffic statistics and link utilization. Consequently, information pertinent to traffic statistics (average rate <i>r</i> and peak rate <i>P</i>) may be determined, and utilization of incoming and outgoing physical links for source-destination pairs may be measured. The control processor <b>201</b> also receives both control messages and control information of data messages. Data messages may be exchanged between source-destination pairs to transport user information. Control messages are messages exchanged between elements or nodes of the network and may be used to establish, maintain or tear down connections. For example, PATH&amp;RESV messages, UPDATE messages and TEAR-DOWN messages of the RSVP protocol may be employed as the control messages. Control messages may also be messages that contain type of service (TOS) bits or TOS addressed metrics, such as is employed in OSPF protocol control messages. Such control messages may include link status and network topology information from other routers.

The output link interface <b>207</b> may also include a transmit buffer and a scheduler for scheduling the transmission of packets onto the output port, which may be implemented by a processor on the corresponding line termination card. Various scheduling methods are available for implementing the scheduling function. Scheduling, such as weighted round-robin scheduling, may be employed for enforcing some types of QoS service commitments. A weight may be described as the fraction of the bandwidth for a particular transmit buffer or queue. Thus, weighting may be employed to control resource allocation among VPNs, among services within VPNs, and among source-destination pairs within the service classes. Weights may be calculated by the routing processor <b>202</b> and downloaded into the control processor <b>201</b> and/or scheduler.

Control processor <b>201</b> detects a condition requiring a new adaptive routing calculation in accordance with the present invention, and hence initiates the path selection process to determine the logical paths of source-destination pairs of the network <b>100</b>. The condition may be termed a "trigger" event, which event is signaled to the routing processor <b>202</b>. The trigger event may be, for example, a router addition/failure or link connect/disconnect. Control processor <b>201</b> may also initiate the path selection process based on a predetermined schedule. The routing processor <b>202</b> provides for an adaptive routing calculation, and also possibly new weighting calculations, to determine new routing provisioning entries and weights based on QoS-guarantee provisioning and network topology information stored within the processing section <b>200</b>. Provisioning entries define logical paths through the network links for different packet flows.

FIG. 3 is a flow chart illustrating the steps of a router providing adaptive routing in accordance with the present invention based on an exemplary network supporting the OSPF protocol. At step <b>301</b>, the adaptive routing is initiated by an internal event (such as by a predetermined schedule) or by an external event (such as by a trigger event). The detected event may initiate an optional step <b>302</b> in which the path-selection process determines a temporary set of provisioning entries according to the SPF routing method. At step <b>303</b>, a multicommodity flow (MCF) routing method is employed for a path-selection process to determine new provisioning entries. The MCF routing method may assign some or all of the new provisioning entries based on the temporary set of provisioning entries. New provisioning entries are determined at step <b>303</b> based on optimization of the SPF routing calculations according to a predefined metric, such as optimized network revenue <i>W</i>.

For example, at step <b>302</b> new routing based on QoS provisioning information and information provided from the provisioning entries of the SPF algorithm may provide an optimized set of provisioning entries for the new routing of classes and packets through network <b>100</b>. New provisioning entries may group packet flows with a given identifier according to classes, with each class having defined QoS commitments. Bandwidth, or other QoS related commitments as metrics, of a given interface card may be allocated and then different classes assigned to the allocated bandwidth.

At step <b>304</b>, the current filter rules of each interface, or line termination, card are deleted for the packet filters that are changed or modified. At step <b>305</b>, the currently defined packet flow identifiers (i.e., a value identifying the specific packet flow, or aggregate of packet flows, that may be based on source and destination addresses) are deleted for each interface, or line termination, card for the packet filters that are changed or modified. At step <b>306</b>, the current class definitions are deleted for each interface, or line termination, card for the packet filters that are changed or modified. The class definitions of each interface or line termination card specify which packet flow classes may be supported by available bandwidth of the interface card.

At step <b>307</b>, bandwidth for each interface, or line termination, card is allocated based on, for example, the available bandwidth of each input line interfaces <b>204</b> and the available bandwidth of each output line interface <b>207</b> (FIG. 2). At step <b>308</b>, new classes are assigned for the given bandwidth allocations determined in step <b>307</b>.

At step <b>309</b>, the new classes generated in step <b>308</b> are installed in each corresponding interface, or line termination, card. At step <b>310</b> defined packet flow identifiers for the classes are installed for each interface, or line termination, card. At step <b>311</b> new filter rules are installed in, for example, the packet classifier <b>203</b>. The filter rules are employed to route packet flows with corresponding identifiers from input ports to output ports of the router based on the actions associated with the filter rule.

The new routing determined by the path-selection process is provided as provisioning entries of a routing table. The provisioning entries of the table are defined for each packet flow (which may be a packet flow or an aggregate of packet flows specified by source and destination address ranges) and a set of classes, each class defined by a set of QoS provisioning commitments. Each routing table for a packet flow has an associated class. An exemplary routing table for a packet flow based on QoS provisioning and network link topology is given in Table 3. <tables id="tabl0004" num="0004"><table frame="all"><title>Table 3</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Label</entry><entry namest="col2" nameend="col2" align="center">Content</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left"><b>src_rtr</b></entry><entry namest="col2" nameend="col2" align="left">The identifier of the source router</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>dst_rtr</b></entry><entry namest="col2" nameend="col2" align="left">The identifier of the destination router</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>src_lint</b></entry><entry namest="col2" nameend="col2" align="left">The input logical interface of the source router</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>dst_lint</b></entry><entry namest="col2" nameend="col2" align="left">The output logical interface of the destination router</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>vpn</b></entry><entry namest="col2" nameend="col2" align="left">The identifier for the client (or VPN) that the packet flow belongs to</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>revenue</b></entry><entry namest="col2" nameend="col2" align="left">Assigned revenue value</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>class</b></entry><entry namest="col2" nameend="col2" align="left">Assigned class</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>w2edelay</b></entry><entry namest="col2" nameend="col2" align="left">Maximum end-to-end delay, in microseconds</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>src_addr_low</b></entry><entry namest="col2" nameend="col2" align="left">Lower bound of the source address range for a packet flow</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>src_addr_high</b></entry><entry namest="col2" nameend="col2" align="left">Upper bound of the source address range for a packet flow</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>dst_addr_low</b></entry><entry namest="col2" nameend="col2" align="left">Lower bound of the destination address range for a packet flow</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left"><b>dst_addr_high</b></entry><entry namest="col2" nameend="col2" align="left">Upper bound of the destination address range for a packet flow</entry></row></tbody></tgroup></table></tables>

As shown in Table 3, the entries <b>src_addr_low</b> and <b>src_addr_high</b> may specify a source address range, and the entries <b>dst_addr_low</b> and <b>dst_addr_high</b> may specify a destination address range. These values may be employed to uniquely identify a packet flow, or aggregate of packet flows. Consequently, these four values may be termed a packet flow identifier (<b>id</b>).

Adaptive routing in accordance with the present invention specifies a class to which the packet flow belongs. This class is associated with a set of QoS commitments that are specified for the class. Table 4 provides an exemplary set of the QoS provisioning commitments for a leaky bucket regulator specified for a class including a packet flow identified by an <b>id</b> value. <tables id="tabl0005" num="0005"><table frame="all"><title>Table 4</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Label</entry><entry namest="col2" nameend="col2" align="center">Type</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left"><i>r</i></entry><entry namest="col2" nameend="col2" align="left">rate in bytes per unit time</entry></row><row><entry namest="col1" nameend="col1" align="left"><i>b</i></entry><entry namest="col2" nameend="col2" align="left">The sender bucket depth</entry></row><row><entry namest="col1" nameend="col1" align="left"><i>P</i></entry><entry namest="col2" nameend="col2" align="left">Peak rate</entry></row><row><entry namest="col1" nameend="col1" align="left"><i>m</i></entry><entry namest="col2" nameend="col2" align="left">minimum packet size (with overhead)</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left"><i>M</i></entry><entry namest="col2" nameend="col2" align="left">maximum packet size (with overhead)</entry></row></tbody></tgroup></table></tables>

The new provisioning entries calculated based on the trigger event are provided to the control processor <b>201</b>, which translates the new routing of source-destination pairs into filter rules. The filter rules are mapped as packet filters downloaded into the packet classifier <b>203</b>. As would be apparent to one skilled in the art, the processing section of FIG. 2 is exemplary only, and many variations on the processing section may be implemented.

An exemplary hardware implementation of the packet filter <b>400</b> of packet classifier <b>203</b> is shown in FIG. 4. Packet filter <b>400</b> performs simple logic operations since hardware elements may perform only a binary-search operation to locate address ranges (intervals) of filter rules including the value of the corresponding address fields of a packet. Packet filter <b>400</b> includes a temporary storage register <b>402</b>, an AND-operator <b>404</b>, processing elements <b>406</b>, and a memory <b>412</b> having interval data registers <b>408</b> storing one or more corresponding bitmaps <b>410</b> associated with each processing element <b>406</b>. Bitmaps <b>410</b> associated with each processing element <b>406</b> each identify the corresponding filter-rules associated with the intervals.

As shown in FIG. 4, a packet received by a router is stored in temporary storage register <b>402</b>, which may be a buffer or register position in a queue. Memory <b>412</b> stores interval data and corresponding bitmaps derived from filter rules, for example Processing elements <b>406</b> each perform a binary search of the corresponding derived intervals for the packet fields. One implementation may employ one processing element <b>406</b> for each filter-rule dimension (address field) comprising a comparator, a state machine and two local registers. For this implementation, the binary search for all stored intervals <b>408</b> by processing elements <b>406</b> is performed in parallel.

Each processing element <b>406</b> returns a bitmap corresponding to an interval including an address field of the received packet. The returned bitmaps are combined by the AND- operator <b>404</b> to form a memory pointer. The result of this search process is a memory pointer to the "best-match" filter rule. The packet filter then performs a further access to memory <b>412</b> to retrieve actions associated with the identified filter rule or filter-rule set (not shown). The packet and corresponding retrieved actions are provided to the route allocation processor <b>206</b>. In exemplary implementations, a packet filter may test for between 512 and 800 filter rules.

FIG. 5 shows a block diagram of an exemplary distributed processing and database (DPD) system <b>500</b> for alternate path routing in accordance with the present invention. DPD system <b>500</b> includes an OSPF processing module <b>512</b> with corresponding link state database <b>510</b>, QoS routing module <b>506</b>, filter rule processing module <b>514</b>, filter management processing module <b>516</b>, and packet classifier module <b>518</b>.

OSPF processing module <b>512</b> receives network topology information through the packet network interface in accordance with the OSPF protocol. Network topology information may typically include, for each router in the packet network <b>100</b>, a router identification address, identification for links connected to the router, other router addresses of other routers connected to the router, and information of other networks (e.g., N₁, N₂, and N₃ of FIG. 1) that may be connected to the router. OSPF processing module <b>512</b> stores the network topology information in the link state database <b>510</b>, and updates the information of the link state database <b>510</b> as new network topology information becomes available, such as when the network topology changes. The OSPF processing module further calculates routing information for the packet network in accordance with the SPF routing method known in the art.

QoS routing module <b>506</b> receives tables having QoS provisioning information for source-destination pairs. The tables are received from the network management database <b>107</b> through network management interface <b>504</b>. The QoS routing module <b>506</b> may also receive both the temporary provisioning entries of the OSPF routing method and the network topology information from the link state database <b>510</b>. Given the QoS provisioning requirements for source-destination pairs, the QoS routing module <b>506</b> recalculates optimized routing of source-destination pairs through the network with the network topology information of the link state database <b>510</b>. The QoS routing module <b>506</b> re-calculates the optimized routing in accordance with the MCF routing method.

Returning to FIG.5, the DPD system <b>500</b> includes network management interface <b>504</b> that retrieves formats data of the network management database <b>109</b>. Communication between network management interface <b>504</b> and network management database <b>109</b> may be mediated by a protocol such as Simple Network Management Protocol (SNMP). Data of the network management database <b>109</b> may be formatted into a record structure of provisioning tables with, for example, reduced entries and in a format that may be desirable for the QoS Routing module <b>506</b>. The packet network interface <b>508</b> formats data received from control packets of the network into a format desirable for the OSPF processing module <b>512</b>.

The processing modules, database and interfaces of the DPD system <b>500</b> may be implemented in the processing section <b>200</b> of FIG. 2. For example, the network management interface <b>504</b>, QoS routing module <b>506</b> and OSPF routing module <b>512</b> with link state database <b>510</b> may be implemented as software of the routing processor <b>202</b>. The packet network interface <b>508</b>, filter rule processing module <b>514</b> and filter management processing module <b>516</b> may be implemented as software of the control processor <b>201</b>. The packet classifier module <b>518</b> may be implemented as hardware of the packet classifier <b>203</b>.

Several methods may be employed to provide shared use by the QoS routing module <b>506</b> and OSPF processing module <b>512</b> of the OSPF routing information and the topology information from the link state database <b>510</b>. First, the QoS routing module <b>506</b> may receive and flatten the OSPF topology information from the link state database <b>510</b> into a separately stored database for use by the QoS routing module <b>506</b>. Second, the QoS routing module <b>506</b> and OSPF processing module <b>512</b> may share a synchronized database access routine. Third, OSPF processing module <b>512</b> may be modified to recognize and employ network topology information from the link state database <b>510</b> stored in a manner consistent with the QoS routing module <b>506</b>. Fourth, when the OSPF processing module <b>512</b> changes topology information from the link state database <b>510</b>, the QoS routing module <b>506</b> may be notified and change its data structure in the same manner.

Since the QoS routing module <b>506</b> calculates routing and path selection with QoS provisioning information, the QoS routing module <b>506</b> may require additional network topology information than that currently collected in accordance with the OSPF protocol. For this case, the control packets as currently employed by the OSPF protocol may be modified to allow for collection of additional features of network topology information. The payload of the OSPF protocol control packets includes a field defined for type of service (TOS) dependent, or addressed, metrics. This field includes several TOS-addressed metrics. The TOS-addressed metrics identify TOS entries in a database or table, with each entry available for use with a TOS metric. Each TOS metric may be a form of control message available to the OSPF protocol. Not all addresses of the database or table of TOS entries of the protocol, however, are currently used for a TOS metric.

For an embodiment of the present invention collecting additional network topology information, the control packets of the OSPF protocol may be modified to define unused TOS entries for adaptive routing. For example, the empty or undefined entries of the TOS-addressed metrics in OSPF packets may be defined to include information such as available link bandwidth (unassigned or assigned but not in use). FIG. 6 shows a line format of an OSPF packet showing the positions of packet type <b>601</b> and TOS bits <b>602</b>, respectively. Consequently, a preferred embodiment of the present invention employs one or more of the TOS entries to convey available bandwidth information on a link (e.g., lowest and highest). In addition, one or more fields of the TOS metrics may be employed to convey information related to available capacity of a link.

Further, one or more TOS entries may be employed to convey information related to routing protocol used in forwarding by a router of network <b>100</b>. For example, the TOS bits may be defined to identify the type of routing available from the router generating the packet, such as adaptive routing in accordance with the present invention, the SPF routing method, or some other form of routing method for the path-selection process. For example, packets arriving at network <b>100</b> may have the defined TOS bits set to specify an unknown or default state. When a router employing adaptive routing in accordance with the present invention receives such a packet, the defined TOS bits are set to indicate a first state.

A router receiving such packet with TOS bits set to the first state and employing adaptive routing (or knows the next logical path for the packet) forwards the packet without changing the values of the TOS bits. A router receiving such packet with TOS bits set to the first state that does not employ adaptive routing (or does not know the next logical path for the packet) changes the TOS bits to a second state and forwards the packet. A router receiving such packet with TOS bits set to the second state forwards the packet in accordance with, for example, a path selected by a default method for the path-selection process (i.e., the SPF routing method).

In addition, preferred embodiments of the present invention may employ a signaling packet conforming to the OSPF protocol. The signaling packet allows a particular router to signal other routers in network <b>100</b> that the particular router supports adaptive routing in accordance with the present invention. Such packet may indicate both a version or manufacturer, for example, and may be termed a QoS advertisement packet. The QoS advertisement packet allows routers employing adaptive routing in accordance with the present invention to predict what routing calculation and path selection may be determined by the particular router associated with the QoS advertisement packet. FIG. 7 shows a line format of an exemplary advertisement packet including advertising router information <b>701</b>. The advertising router information <b>701</b> may include information related to the path-selection process and the routing protocol employed by the router originating the advertisement packet.

Some embodiments of the present invention may include a method of ensuring that all routers of the network <b>100</b> determine the same sets of provisioning entries by using similar network topology information. Such method may be required when, for example, a router is added to the network, or if some other event causes the network topology information to change. When such a change occurs, the routers of the network may not each contain the same network topology information in link state database <b>510</b>.

The mismatch between the link state database <b>510</b> of each of the various routers of network <b>100</b> may require a distributed database commit operation to synchronize the information of the databases. A distributed database commit operation provides signaling between elements of a distributed database to ensure that all elements are modified according to the most recent network topology information. A distributed database commit operation may be employed when relatively frequent updates of a database occur (e.g., when there is high likelihood of network failure, elements or routers are added to the network, or considerably high provisioning activity from a centralized point of command). For the present invention, such distributed database commit operation may require an exchange of packets between routers of the network <b>100</b> to verify that each router has determined the same provisioning entries.

As shown in FIG. 7, the exemplary advertisement packet may be employed for the distributed database commit operation as a means for broadcasting path-selection and other routing information determined by particular routers, which in turn reflects a state of the topology information in each link state database. The advertising router information <b>701</b> that may be employed to predict what routing calculation and path selection may be determined by the particular router associated with the QoS advertisement packet. The QoS advertisement packet may also include the provisioning entry information for running and candidate sets of provisioning entries <b>705</b> and <b>706</b>. The provisioning entry information may be included in a HASH table format. In addition, a working set of provisioning entries <b>707</b> may also be included, the working set being used to signal to other router the provisioning entries that may be modified by network re-configuration commands.

Returning to FIG. 5, once the previously described information is available, the QoS routing module <b>406</b> classifies existing packet flows through the packet network <b>100</b> into real-time (requiring immediate throughput) and non-real-time (can tolerate delay) packet flows, which classification may be based on a delay threshold. End-to-end delays are calculated and divided into per-hop delays (delay through the link between routers) Real-time and non-real-time packet flows have effective bandwidth requirements assigned for each packet flow, and the packet flows are then further classified into multiplexable or non-multiplexable flows, depending on whether the packet flow occupies more than a predetermined level of bandwidth of the link traversed.

The total available capacity C is allocated to the multiplexable or nonmultiplexable flows. Then, routing calculations and path selections are determined for the multiplexable or non-multiplexable flows based on a corresponding routing mechanism. For example, the multiplexable flows may have path selection based on a multicommodity flow (MCF), or QoS-based, routing method, such as TALISMAN, available from Lucent Technologies, Murray Hill, New Jersey. The non-multiplexable flows may have path selection based on a lossless effective bandwidth algorithm, such as the SPF routing method.

Adaptive routing in accordance with the present invention receives QoS information and network topology information mediated by the OSPF protocol to calculate the new routing tables. The calculation of new routing tables preferably completes within a time that enables existing packet flows to be re-routed before tear-down of established connections in accordance with a high-level protocol. To this end, some tables for re-routing may be pre-computed prior to use.

QoS routing module <b>406</b> may employ a method for allocating resources and determining provisioning entries as shown in FIG. 8. First, at step <b>801</b>, each packet flow is classified as a real-time flow or non-real-time flow based on the end-to-end delay of the packet flow compared to a predetermined delay threshold. Next, at step <b>802</b> per-hop, or nodal, delays <i>d</i>_<i>p</i> are calculated for each packet flow (e.g., delay between routers). Per-hop delays <i>d</i>_<i>p</i> are calculated by dividing the end-to-end delay for the packet flow by the maximum number of hops <i>n</i>_<i>MAX</i> for the packet flow. For real-time flows, <i>n</i>_<i>MAX</i> is one plus the minimum number of hops <i>n</i>_<i>MIN</i>. For non-real-time flows, <i>n</i>_<i>MAX</i> is a laxity factor plus the minimum number of hops <i>n</i>_<i>MIN</i>.

Once the per hop delays are calculated, at step <b>803</b> the effective bandwidth value <i>ed</i>_<i>o</i>, of each packet flow is determined using the nodal delays <i>dp</i> and QoS information. For example, QoS information may be specified for a class the packet flow belongs to, and may include average token (packet) rate <i>r</i>, peak rate <i>P</i>, and the buffer size <i>B</i>_<i>token</i> if a leaky bucket regulator is employed by the node. For example, if a node has a buffer size <i>B</i>_<i>node</i> and output link capacity <i>C</i>_<i>trans</i>, the effective bandwidth value <i>ed</i>_<i>o</i> of each packet flow may be calculated as in equation (1):<maths id="math0001" num=""><img file="EP1035751A2_D0003.tif" /></maths> where <maths id="math0002" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">buf</mtext></mrow></msub><mtext>=(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">node</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic"> C</mtext></mrow><mrow><mtext mathvariant="italic">trans</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1035751A2_D0004.tif" /></maths> (the maximum delay time of the node's buffer), <maths id="math0003" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">=(B</mtext></mrow><mrow><mtext mathvariant="italic">token</mtext></mrow></msub><mtext></mtext><mtext mathvariant="italic">r</mtext><mtext>)</mtext></mrow></math><img file="EP1035751A2_D0005.tif" /></maths>, and <maths id="math0004" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">token</mtext></mrow></msub><mtext mathvariant="italic"> (P-r)</mtext><mtext>)</mtext></mrow></math><img file="EP1035751A2_D0006.tif" /></maths>.

At step <b>804</b> the packet flows are then classified as multiplexable (packet flows that may be mixed with other flow traffic on one or more links) or non-multiplexable (packet flows that are desirably assigned a dedicated link and dedicated capacity) based on comparison of the corresponding effective bandwidth <i>ed</i>_<i>o</i> values with a multiplexing threshold. The multiplexing threshold may be calculated by, for example, an examination of the statistical properties of the network traffic flows at peak levels.

At step <b>805</b> bandwidth is reserved from the total available capacity <i>C</i> for routing of packet flows exhibiting characteristics of high-volume traffic and non-multiplexable flows. High-volume traffic may be defined based on the maximum bandwidth (or peak rate <i>P</i>) of the packet flows. For these high-volume traffic and non-multiplexable packet flows, provisioning entries determined by the shortest-path routing of OSPF may be employed for routing of the packets through the node.

At step <b>806</b> the residual bandwidth <i>C</i>_<i>MUX</i> for multiplexable packet flows is determined. The residual bandwidth <i>C</i>_<i>MUX</i> may be determined as the available capacity <i>C</i> minus the sum of the effective bandwidth values <i>ed</i>_<i>o</i> of the non-multiplexable packet flows. Alternatively, the residual bandwidth <i>C</i>_<i>MUX</i> may be determined as the total available capacity <i>C</i> minus the capacity reserved for non-multiplexable packet flows.

At step <b>807</b>, an initial route is determined for each multiplexable packet flow based on requirement of the effective bandwidth value <i>ed</i>_<i>o</i>, which requirement is determined by mapping the effective bandwidth value <i>ed</i>_<i>o</i> to allowed rates of the output links of the node. The initial routes may also be determined, for example, with the SPF routing method.

At <b>808</b>, routing for the multiplexable packet flows is calculated with a multicommodity flow (MCF) routing method. The routing is provided as a table having a candidate set of provisioning entries.

The method as shown in FIG. 8 employs the QoS provisioning information, the link state topology, and the packet flow classifications (real-time/non-real-time and multiplexable/non-multiplexable packet flows) to form provisioning entries for routing of packets through the node (router). Such provisioning entries may define specific source and source port address ranges of packets to be routed to other specific destination and destination port address ranges. Further, the packet network <b>100</b> may employ a protocol, such as the Type of Service (TOS) bits and/or RSVP control messages, to allocate resource reservation over physical and logical links for the corresponding packet flows.

The path-selection process of QoS routing module <b>506</b> provides an optimized routing of source-destination pairs to the filter rule processing module <b>514</b> as a table having set of candidate provisioning entries. The set of candidate provisioning entries may be employed as information from which filter rules are derived. In accordance with the present invention, the actions of the filter rule are defined so as to route packets through a routing fabric of the router based on the newly determined path selection. Given the source and destination address ranges (and possibly the protocol identifier and TOS specification) of a selected filter rule applicable to a received packet, the corresponding action associated with the filter rule is applied to the packet. The action associated with a filter rule may be to route the received packet of the packet flow having header field values included in the corresponding source and destination address ranges from specific input ports to specific output ports of the router.

Each filter rule comprises a classifier specification and an action. The classifier specification defines ranges of source addresses, destination addresses, source port ranges, and destination port ranges, and may be the packet flow identifier (<b>id</b>) as described previously. A protocol identifier and TOS specification may also be associated with the filter rule. Consequently, the filter rules are preferably constructed as rectangles in a four, five or six dimensional space (i.e, a <i>k</i>-dimensional space, <i>k</i> an integer greater than one corresponding to the number of unique fields used for packet routing). As would be apparent to one skilled in the art, higher dimensional spaces may be employed as the packet filter processes more packet header field values. The filter-rule rectangles may overlap. The particular filter rule that is applied to an incoming packet when the filter-rule rectangles overlap may be determined from a priority assigned to each filter rule.

When a packet arrives, the determination of which filter rule to apply to the packet is a point location problem in the <i>k</i>-dimensional space. The packet classifier solves the point location problem, as described subsequently, and the actions associated with a particular filter rule are retrieved from memory. An exemplary set of provisioning entries for a filter rule may be as given in Table 5. <tables id="tabl0006" num="0006"><table frame="all"><title>Table 5</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Label</entry><entry namest="col2" nameend="col2" align="center">Type</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">id</entry><entry namest="col2" nameend="col2" align="left">The index of source-destination pairs for the packet flow (note that when ranges are specified, the packet flow may be an aggregate of packet flows)</entry></row><row><entry namest="col1" nameend="col1" align="left">rtr</entry><entry namest="col2" nameend="col2" align="left">The next-hop router that is employed for packet forwarding</entry></row><row><entry namest="col1" nameend="col1" align="left">src_port</entry><entry namest="col2" nameend="col2" align="left">The input port of the logical interface of the router</entry></row><row><entry namest="col1" nameend="col1" align="left">dst_port</entry><entry namest="col2" nameend="col2" align="left">The output port of the logical interface of the router</entry></row><row><entry namest="col1" nameend="col1" align="left">bw</entry><entry namest="col2" nameend="col2" align="left">The amount of bandwidth reserved for the packet flow</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">b</entry><entry namest="col2" nameend="col2" align="left">The size of the local buffer for the packet flow</entry></row></tbody></tgroup></table></tables>

Table 5 includes the <b>id</b> field that is the packet flow identifier, and is associated with the routing actions of the table. The entries of Table 5 may define actions such as cross-connection between logical port interfaces of the router for a given packet flow. In addition, the QoS commitment for the packet flow, such as required bandwidth and buffer size is specified. The <b>id</b> field value of Table 5 identifies specific source and destination address ranges, as shown in Table 6. <tables id="tabl0007" num="0007"><table frame="all"><title>Table 6</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Label</entry><entry namest="col2" nameend="col2" align="center">Type</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left"><b>src_addr_low</b></entry><entry namest="col2" nameend="col2" align="left">Lower bound of the source address range for a packet flow</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>src_addr_high</b></entry><entry namest="col2" nameend="col2" align="left">Upper bound of the source address range for a packet flow</entry></row><row><entry namest="col1" nameend="col1" align="left"><b>dst_addr_low</b></entry><entry namest="col2" nameend="col2" align="left">Lower bound of the destination address range for a packet flow</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left"><b>dst_addr_high</b></entry><entry namest="col2" nameend="col2" align="left">Upper bound of the destination address range for a packet flow</entry></row></tbody></tgroup></table></tables>

The fields of Table 6 may further include the TOS specification and/or protocol identifier.

Filter rule processing module <b>514</b> of FIG. 5 creates the new filter rules based on these new provisioning entries. The new set of provisioning entries and corresponding filter rules are then provided to the filter management module <b>516</b>, which also retains copies of running filter rules corresponding to the currently used, or "running" set of provisioning entries employed by the packet classifier module <b>518</b>. A running set of provisioning entries, and corresponding running set of filter rules, are generated by the determined path selections prior to reconfiguration and routing re-calculation.

The filter management module <b>516</b> compares the new and running sets of filter rules, and selectively determines filter-rules to be deleted from the packet classifier module and filter rules that are to be modified. Once the selected filter-rules to be deleted or modified are determined, the filter management module <b>516</b> substitutes the selected packet filter rules into the packet classifier module <b>518</b>. For the exemplary embodiment, the packet classifier module <b>518</b> may be employed by the packet classifier <b>203</b> (FIG. 2) to cause specific routing of packets within the routing fabric, such as by providing control signals provided to the route allocation processor <b>206</b>.

As described previously, packet classifier module <b>518</b> receives filter rules from the filter management module <b>514</b>, and applies the filter rules to the incoming packets. FIG. 9 illustrates the process of packet filtering on two packet fields, corresponding to a point location in 2-dimensions. A point location in 2-dimensions may be a location of a point within a particular filter-rule rectangle defined by source and destination address ranges. As would be apparent to one skilled in the art, the 2-dimensional point location maybe extended to higher dimensions, such as the 4-dimensional point location, with filter-rule rectangles further defined by source port address ranges and destination port ranges. As shown in FIG. 9, four overlapping filter rules operating on, for example, the source address field and the destination address field of a received packet are represented by overlapping 2-dimensional rectangles <b>901-904</b>. The filter rule segments of the rectangles <b>901-904</b> are projected as intervals labeled X0-X8 and Y0-Y7 on the corresponding dimension axes X (for source address) and Y (for destination address). The intervals and bitmaps may be defined similarly to those described with respect to FIG. 4.

In the example shown in FIG. 9, segments of the four filter rules in each dimension overlap the six intervals on the Y-axis and seven intervals on the X-axis, respectively. For a worst case, the projection results in a maximum of 2<i>n</i> - 1 intervals on each axis for the dimension, where <i>n</i> is the number of filter rules. For the example, <i>n</i> is four filter rules, resulting in the worst case of seven intervals on the X-axis. Bitmap arrays <b>910</b> and <b>912</b> associated with each dimension are formed having bitmaps for each interval. A bit in the bitmap is set if, and only if, the rectangle corresponding to the bit position overlaps with the interval that the bitmap corresponds to. For example, interval Y1 has a corresponding bitmap <b>914</b>. Since rectangle <b>901</b> overlaps interval Y1, the bit at the first bit-position is set to logic "1". None of the rectangles <b>901-904</b> may overlap with, for example, only half an interval because of the method by which the intervals are defined. The bitmaps may be stored as one or more bitmaps having associated interval bitmap pointers.

A packet arrives to the packet filter of the router. The packet may have several fields, but two field values, E₁ and E₂, one per dimension, form coordinates of a point <i>EP</i> for point-location in 2-dimensions. E₁ may be a source address, and E₂ may be a destination address. Intervals are located on each dimension axis X and Y that include the corresponding field values of the point <i>EP</i>. In the example, these are intervals X5 and Y4 for the X-axis and Y-axis, respectively. The interval bitmaps <b>916</b> and <b>915</b> of intervals X5 and Y4, respectively, are employed to locate the highest priority rectangle that covers this point. The interval bitmaps <b>916</b> and <b>915</b> may be reconstructed from a retrieved bitmap and corresponding interval bitmap pointers. Rectangles <b>901-904</b> may be numbered and allocated bit-positions in the interval bitmap based on their priorities, with rectangle <b>901</b>, for example, being the lowest priority and rectangle <b>904</b> being the highest priority. After the combination of the interval bitmaps in step <b>904</b>, the first bit set to logic "1" in the resulting filter-rule bitmap is the bit identifying the highest priority rectangle <b>904</b> amongst all those rectangles overlapping the point <i>EP</i> in the example shown in FIG. 9.

For the preferred embodiments of the present invention, the QoS routing module <b>506</b> employs a MCF routing method. However, the MCF routing method is derived from general routing optimization, and may be preferred if new, optimized routing is desirably determined in real time. The following describes the general routing optimization method, and then the MCF routing algorithm. The general routing optimization method includes methods based on both stochastic and deterministic routing optimizations. The general routing optimization method and the MCF routing algorithm are similar to those methods employed in network design tools. Such network design tools employ, for example, the method described in D. Mitra et al., "ATM Network Design and Optimization: A Multirate Loss Network Framework," <u>IEEE/ACM Transactions on Networking 4</u> (August 1996) 531-543 (herein referred to as "Mitra et al."). The stochastic routing optimization and MCF routing methods of Mitra et al. may be employed with virtual private network design tools, such as TALISMAN available from Lucent Technologies, of Murray Hill, N.J. The present invention is not so limited to the following method, and any routing method may be employed which calculates optimized routing paths through packet network <b>100</b> based on QoS provisioning information and network topology information.

The general routing optimization method determines rates of traffic offered to each route between a source-destination pair that optimize performance (also known in the art as the optimum routing problem) of the network <b>100</b> according to predefined optimization criteria that includes QoS provisioning information. The performance of the network may be characterized in various ways. For example, performance is desirably characterized by the value of the long-term network revenue <i>W</i>. Long-term network revenue <i>W</i> may be defined as the weighted measure of carried bandwidth on the network constrained such that each source-destination pair earns a minimum amount of revenue. Revenue <i>W</i> is determined by the revenue earned per carried connection per unit time <i>e</i>_<i>sr</i> and the traffic rate (also referred to as "traffic intensity").

The subscript <i>s</i> (<i>s</i> an integer greater than 0) represents each service type, and signifies that each service type has its own particular set of values for these parameters. In the art of network design and management, the traffic characteristics and measures of quality of service may be determined by the pertinent "application," and the term "service" is used somewhat more narrowly. For the following, the term "service" is employed in a general sense, in which it includes or is synonymous with the term "application". A class, or possibly a super-class, may be a service. The subscript <i>r</i> (<i>r</i> an integer greater than 0) represents each route in the set of permissible routes between a given source-destination pair, and signifies that even within a given service type <i>s</i>, each route has its own particular set of values.

Given these definitions, a general routing optimization may be formulated as joint maximization of network revenue by considering all offered traffic to the network. FIG. 10 illustrates an exemplary flowchart for the general routing optimization. At step <b>1001</b>, initial values are provided to define the network topology and network traffic characteristics. Initial values include stream, or packet flow, identifiers, bandwidth, and port definitions for each node <i>n</i> of the set of nodes <i>N,</i> 1 ≤ <i>n ≤ N</i> and each lin<i>k l</i> of the set of links <i>L</i>, 1 ≤ <i>l ≤ L</i>. Initial values also include predefinitions (e.g., QoS provisioning commitments) for each service class <i>s</i> of the set of services <i>S,</i> 1 ≤ <i>s ≤ S,</i> the effective bandwidth <i>ed</i>_<i>sl</i> of each service class <i>s</i> on each link <i>l</i>, the demand for each service class between each source-destination pair σ, the route sets <b>R</b>(<i>s</i>, σ), for packet flows (<i>s</i>, σ), and the capacity allocation <i>C</i>_<i>l</i> on the respective link <i>l</i>. Note that these initial values may be defined or determined as described with respect to FIG. 8.

At step <b>1002</b>, an initial value for the network revenue <i>W</i> is provided. The value for <i>W</i> may be predetermined through network simulations, heuristic methods, or previous or current values measured prior to network reconfiguration and/or re-routing calculation.

At step <b>1003</b>, initial values are provided as current estimates for the traffic rates, The initial values for the traffic rates may be predetermined through network simulations, heuristic methods, or previous or current values measured prior to network reconfiguration and/or re-routing calculation.

At step <b>1004</b>, network performance of routing is determined from the current estimates for the traffic rates, the initial value for the network revenue <i>W</i>, and the initial values for the parameters provided in step <b>1001</b>.

At step <b>1005</b>, the values of the current estimates for the traffic rates are incremented according to, e.g., the method of steepest ascent. At step <b>1006</b>, a current value of <i>W</i> is calculated.

At step <b>1007</b>, in an exemplary method of measuring the approach to a local optimum, convergence to the optimum value of network revenue <i>W</i> is performed by comparing the difference between current and previous values of <i>W</i>. If the difference is less than a predefined threshold, the iterative procedure may be defined as being converged to an estimate for the optimum value fo<i>r W</i>. If <i>W</i> is less than the predetermined threshold, at step <b>1008</b> the current values of <i>W</i> and the current estimates for the traffic rates are provided as the optimum output values. The predefined threshold may be determined off-line through network simulation or other methods known in the art. Otherwise, the procedure is iterated, by returning to step <b>1004</b>, using the current estimates for the traffic rates as input values.

The MCF routing method is derived from a simplification to the general routing optimization with stochastic variables. Consequently, the general routing optimization with stochastic variables is first described. The general stochastic routing method derived with stochastic variables is as follows. The traffic intensity is defined as the mean arrival rate of connection requests offered (i.e., to be established) to the given route multiplied by the mean holding period of a connection. Arrivals of connection requests may follow a Poisson distribution. Related to the traffic intensity is the offered traffic rate <i>ρ</i>_<i>sr</i> to a route <i>r</i> for a service class <i>s</i>. The loss probability is defined as that fraction of connections that are not established, or "blocked", for a given link or route. Blocking occurs if any link in the route refuses to establish the connection due to insufficient resources to carry the connection on that link.

Loss probabilities may exhibit dependence on the offered traffic rates <i>ρ</i>_<i>sr</i>. Consequently, small changes in traffic loading in one portion of the network may have effects over a larger portion of the network. Loss probabilities may be determined from the relationship between link loss probabilities <i>B</i>_<i>sl</i> (probability of loss of service <i>s</i> on a link <i>l</i>) and route loss probabilities <i>L</i>_<i>sr</i> (probability of loss of service <i>s</i> on route <i>r</i>). Therefore, an iterative method may be employed to determine an estimate of the optimal set of offered traffic rates <i>ρ</i>_<i>sr</i> by successive approximations. Successive approximation may employ an approach based on well-known techniques of optimization, such as the method of steepest ascent. According to this method, knowledge of the sensitivity of network revenue <i>W</i> to each of the various parameters such as rates of traffic offered to the routes (the offered traffic rates <i>ρ</i>_<i>sr</i>), is used to formulate the next estimate (approximation) for the current estimate (approximation). These sensitivities of network revenue <i>W</i> to each of the various parameters (∂<i>W</i>/∂<i>ρ</i>_<i>sr</i>) are collectively referred to as the "network sensitivities."

An arriving connection request of a given packet flow may be offered to any route in the set of permissible routes for that packet flow. These arriving connection request offers may be approximately distributed over the routes of the route set according to respective, predetermined probability values. That is, for each route, the probability that a randomly selected connection will be offered to that route has a predetermined value. The optimized values of the parameters <i>ρ</i>_<i>sr</i> are employed to determine these probability values.

General routing optimization with stochastic variables is now described referring to FIG. 10. At step <b>1001</b>, the initial values are provided to define the network topology and network traffic characteristics, and, at step <b>1002</b>, an initial value for the network revenue <i>W</i> is provided. At step <b>1003</b>, an initial set of values are provided as current estimates for the traffic rates, <i>ρ</i>_<i>sr</i>.

At step <b>1004</b>, route loss probabilities <i>L</i>_<i>sr</i> and network sensitivities ∂<i>W/</i>∂<i>ρ</i>_<i>sr</i> are determined from the current estimates for the traffic rates <i>ρ</i>_<i>sr</i>, the initial value for the network revenue <i>W</i>, and the initial values for the parameters provided in step <b>1001</b>

At step <b>1005</b>, the values of the current estimates for the <i>ρ</i>_<i>sr</i> are incremented according to, e.g., the method of steepest ascent. At step <b>1006</b>, a current value of <i>W</i> is calculated as in equation (2).<maths id="math0005" num=""><img file="EP1035751A2_D0007.tif" /></maths>

At step <b>1007</b>, convergence to the optimum value of network revenue <i>W</i> is determined. If the difference is less than a predefined threshold, the iterative procedure may be defined as being converged to an estimate for the optimum value for <i>W</i>. If <i>W</i> is less than the predetermined threshold, at step <b>1008</b> the current values of <i>W</i> and the current estimates of <i>ρ</i>_<i>sr</i> are provided as the optimum values of <i>W</i> and <i>ρ</i>_<i>sr</i>. Otherwise, the procedure is iterated, by returning to step <b>1004</b>, using the current estimates of <i>ρ</i>_<i>sr</i> as input values.

At step <b>1004</b> of FIG. 10, the performance of the determined routing and network sensitivities are determined by calculating the loss probabilities <i>L</i>_<i>sr</i> and the network sensitivities ∂<i>W</i>/∂<i>ρ</i>_<i>sr</i>. The network sensitivities may preferably be defined as the respective derivatives of network revenue with respect to the offered load of service types on route <i>r</i>. The link loss probabilit<i>y B</i>_<i>sl</i> of each service type <i>s</i> on each link <i>l</i> may be generated at step <b>1004</b> of FIG. 10. Procedures known in the art may be employed to derive, from the link loss probability <i>B</i>_<i>sl</i> and other information generated in the iterative procedure, a measure of the desired bandwidth utilization for each link of each service route. The desired bandwidth utilization may then be employed to determine nominal allocations of bandwidth for each packet flow, or packet flow, to each link of each service route. Such procedures are described in, for example, Elwalid et al. and Mitra et al.

The step <b>1004</b> of FIG. 10 for general routing optimization with stochastic variables is shown in FIG. 11. The step <b>1004</b> of FIG. 11 is shown as a method of five steps, shown respectively as steps <b>1101</b>, <b>1102</b>, <b>1103</b>, <b>1104</b>, and <b>1105</b>. At step <b>1101</b>, a self-consistent solution of two systems of coupled equations (for each service class <i>s</i> and link <i>l</i>) is solved for the predefined effective bandwidths <i>ed</i>_<i>sl</i>, the predefined link capacities <i>C</i>_<i>l</i>, and the current estimates of the offered traffic loads <i>ρ</i>_<i>sr</i>. The step <b>1101</b> may include a determination of the link loss probability <i>B</i>_<i>sl</i> of calls of service <i>s</i> on link <i>l</i>. Since each route <i>r</i> carrying traffic of service type <i>s</i> and using link <i>l</i> adds the load ν_<i>sl;r</i> on link <i>l</i> (which added load may follow a Poisson distribution), the added load may be at a rate that is reduced by independent traffic thinning (i.e., dropping of connections) by all other links in the route. By summing the added loads ν_<i>sl;r</i> over all routes <i>r</i> which use link <i>l</i>, the total thinned, or reduced, load of service <i>s</i> offered to link <i>l</i> is ν_<i>sl</i>. The reduced load with link independence is given in equation (3):<maths id="math0006" num="(3)"><math display="block"><mrow><msub><mrow><mtext>ν</mtext></mrow><mrow><mtext mathvariant="italic">sl</mtext></mrow></msub><mtext> = </mtext><apply>&lt;sum /&gt;<lowlimit><mtext>σ</mtext></lowlimit>&lt;uplimit /&gt;<mrow><mtext></mtext><apply>&lt;sum /&gt;<lowlimit><mtext mathvariant="italic">r</mtext><mtext>∈</mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><mtext mathvariant="italic">s</mtext><mtext>,σ)</mtext><mtext mathvariant="italic">l</mtext><mtext>∈</mtext><mtext mathvariant="italic">r</mtext></lowlimit>&lt;uplimit /&gt;<mrow><msub><mrow><mtext> ρ</mtext></mrow><mrow><mtext mathvariant="italic">sr</mtext></mrow></msub><mtext></mtext><apply>&lt;product /&gt;<lowlimit><mtext mathvariant="italic">m</mtext><mtext>∈</mtext><mtext mathvariant="italic">r</mtext><mtext>-{</mtext><mtext mathvariant="italic">l</mtext><mtext>}</mtext></lowlimit>&lt;uplimit /&gt;<mrow><mtext> (1-</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">sm</mtext></mrow></msub><mtext>)</mtext></mrow></apply></mrow></apply></mrow></apply></mrow></math><img file="EP1035751A2_D0008.tif" /></maths>

In addition, the B_<i>sl</i> may be determined from equation (1) and expressed as a mapping φ_<i>sl</i> of the set of total thinned loads per link<maths id="math0007" num=""><img file="EP1035751A2_D0009.tif" /></maths> for all services <i>s</i> (1≤ <i>s</i> ≤ <i>S</i>).

The step <b>1101</b> may employ an interative method to solve these coupled equations, referred to as fixed-point equations (FPE). For the set of all routes <b>R</b>(s,σ), one system of equations defines the set of link loss probabilities <i>B</i>_<i>sl</i> and is given in equation (4), and the other system defines the set of offered loads ν_<i>sl</i> and is given in equation (5).<maths id="math0008" num=""><img file="EP1035751A2_D0010.tif" /></maths> where<maths id="math0009" num=""><img file="EP1035751A2_D0011.tif" /></maths> (for all links <i>l</i> (1 ≤ <i>l</i> ≤ L)), and<maths id="math0010" num=""><img file="EP1035751A2_D0012.tif" /></maths> (for all services <i>s</i> (1 ≤ <i>s</i> ≤ <i>S</i>) and links <i>l</i> (1 ≤ <i>l</i> ≤ <i>L</i>)), and Ψ is the mapping set {φ_<i>sl</i>}_<i>sl</i> for all services <i>s</i> (1 ≤ <i>s</i> ≤ <i>S</i>) and for all links <i>l</i> (1 ≤ <i>l</i> ≤ <i>L</i>).

At step <b>1102</b>, the route loss probabilities <i>L</i>_<i>sr</i> are determined from the relationship as given in equation (6):<maths id="math0011" num="(6)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">sr</mtext></mrow></msub><mtext> = 1 - </mtext><apply>&lt;product /&gt;<lowlimit><mtext mathvariant="italic">l</mtext><mtext>∈</mtext><mtext mathvariant="italic">r</mtext></lowlimit>&lt;uplimit /&gt;<mrow><mtext> (1-</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">sl</mtext></mrow></msub><mtext>)</mtext></mrow></apply></mrow></math><img file="EP1035751A2_D0013.tif" /></maths>

Step <b>1103</b> then determines the derivative of the link loss probability <i>B</i>_<i>sl</i> with respect to each of the total thinned loads ν_<i>sl</i> as given in equation (7):<maths id="math0012" num=""><img file="EP1035751A2_D0014.tif" /></maths> where <i>t</i> is a dummy variable index, <b>ed</b>_<i>l</i> is the set of effective bandwidths {<i>ed</i>_<i>sl</i>} for all services <i>s</i> on link <i>l</i>, ν_<i>l</i> is the set of thinned {ν_<i>sl</i>} for all services <i>s</i> on link <i>l</i>, and <i>C</i>_<i>l</i> is the capacity of link <i>l</i>.

At step <b>1104</b>, a set of parameters <i>c</i>_<i>sl</i> is calculated for each service class <i>s</i> and each link <i>l</i>. These parameters, which may be defined as implied costs, reflect the effective loss of revenue occasioned when the carrying of connections of a given service class <i>s</i> on a given link <i>l</i> reduces the remaining capacity and thus leads to an incremental increase in the blocking of future offered calls. The predefined network revenue <i>e</i>_<i>sr</i> earned per carried connection per unit time, and the route loss probability <i>L</i>_<i>sr</i>, which is the equilibrium probability that after admission to the network, a connection of service class <i>s</i> will be dropped by route <i>r</i> (a route will drop a call if any of its links refuses the call) are provided as input values to step <b>1104</b>. At step <b>1104</b>, the parameters <i>c</i>_<i>sl</i> are determined from the relationship as given in equation (8) (where <i>t</i> is a dummy variable index over <i>s</i>):<maths id="math0013" num=""><img file="EP1035751A2_D0015.tif" /></maths> Equation (8) represents a system of(S X L) linear equations that may be solved for the set of parameters <i>c</i>_<i>sl</i>. The complexity of the calculations required to solve equation (8), using exact techniques, may be <i>O</i>(<i>S</i>^<i>3</i><i>L</i>^<i>3</i>) (here <i>O</i>() is the mathematical term "on the order of").

The calculation of network sensitivities ∂<i>W</i>/∂ρ_<i>sr</i> is performed at step <b>1105</b>. The network sensitivities ∂<i>W</i>/∂ρ_<i>sr</i> are then readily derived from the route loss probabilities <i>L</i>_<i>sr</i>, the earnings parameters <i>e</i>_<i>sr</i>, and the implied costs <i>c</i>_<i>sl</i> as shown in equation (9):<maths id="math0014" num="(9)"><math display="block"><mrow><mtext>∂</mtext><mtext mathvariant="italic">W</mtext><msub><mrow><mtext>/∂ρ</mtext></mrow><mrow><mtext mathvariant="italic">sr</mtext></mrow></msub><mtext> = (1- </mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">sr</mtext></mrow></msub><mtext>)</mtext><mfenced open="(" close=")"><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext mathvariant="italic">sr</mtext></mrow></msub><mtext> - </mtext><apply>&lt;sum /&gt;<lowlimit><mtext mathvariant="italic">l</mtext><mtext>∈</mtext><mtext mathvariant="italic">r</mtext></lowlimit>&lt;uplimit /&gt;<mrow><mtext></mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext mathvariant="italic">sl</mtext></mrow></msub></mrow></apply></mrow></mfenced></mrow></math><img file="EP1035751A2_D0016.tif" /></maths>

In many cases of practical importance, the link capacities may become so great that it is not economically or numerically feasible to solve the FPE as given by equation (4) and equation (5) to find the implied costs by exact techniques. If the calculation employs exact techniques, the calculation of the link loss probabilities <i>B</i>_<i>sl</i> may have complexity <i>O</i>(<i>C</i>), where <i>C</i> characterizes the link capacities.

In such cases, as described in Mitra et al., an asymptotic approximation referred to as the Uniform Asymptotic Approximation (UAA) method may be used to reduce the complexity of the calculations. In addition, various values for groups of small links may be determined by exact techniques while, concurrently, various values for groups of larger links may be determined by the UAA method. Such an approach may be termed a "hybrid" approach.

When the UAA method is employed, solving the fixed-point equations may require less computational complexity, and hence may require less time to perform the computations. The complexity of calculating the link loss probabilities may be reduced to O(1) (i.e., it remains bounded as <i>C</i> increases without bound), and the complexity of finding the implied costs may be reduced to <i>O</i>(<i>L</i>^<i>3</i>). Thus, the complexity of finding the implied costs is made independent of the number of service classes. This is especially significant for large multirate networks that serve customers with diverse needs and thus carry traffic in many different service classes.

Although the UAA method may be preferred for the stochastic optimization as addressed in Mitra et al., different asymptotic approximation techniques may be employed when solving the stochastic optimization in the context of the present invention, such as the Refined Uniform Asymptotic Approximation (RUAA) method as described in J.A. Morrison, K.G. Ramakrishnan, and D. Mitra, "Refined Asymptotic Approximations to Loss Probabilities and Their Sensitivities in Shared Unbuffered Resources," SIAM J. APPL. MATH. 59 Number 2, November 1998, 494-513. The RUAA method may be preferred as more accurate for calculating implied costs and sensitivities to link loss probabilities.

However, since the present invention relates to adaptive routing in which new network routing is determined in real time, the stochastic optimization of the UAA and RUAA methods may not necessarily provide adequate performance. Consequently, the preferred embodiments of the present invention employ the MCF routing method as derived from a simplification to the general routing optimization with stochastic variables. The simplification removes the characteristics of randomness and stochastic variables from the stochastic system. The connection request arrival and connection holding times are considered as deterministic variables (deterministic traffic rates defined as χ_<i>sr</i>), while the packet flows are considered as static or infinite duration fluids or flows. With this simplification, the optimum routing problem is considered as a linear programming problem (a large system of linear functions of unknowns and linear objective function).

General routing optimization with the MCF routing method is now described referring to FIG. 10. At step <b>1001</b>, the initial values are provided to define the network topology and network traffic characteristics, and, at step <b>1002</b>, an initial value is provided for the network revenue <i>W</i>, approximated by maximized deterministic revenue <i>W</i>_<i>F</i> (defined below). At step <b>1003</b>, an initial set of values are provided as current estimates for the traffic rates, <i>χ</i>_<i>sr</i>. The initial set of values for the traffic rates <i>χ</i>_<i>sr</i> may be predetermined through network simulations, heuristic methods, or previous or current values measured prior to network reconfiguration and/or re-routing calculation.

At step <b>1004</b>, the performance of the network routing and network sensitivities are determined from the current estimates for the traffic rates <i>χ</i>_<i>sr</i>, the initial value for the network revenue <i>W</i>_<i>F</i>, and the initial values for the parameters provided in step <b>1001</b>.

At step <b>1005</b>, the values of the current estimates for the <i>χ</i>_<i>sr</i> are incremented according to, e.g., full pricing. At step <b>1006</b>, a current value of <i>W</i>_<i>F</i> is calculated.

At step <b>1007</b>, in an exemplary method of measuring the approach to a local optimum, convergence to the optimum value of network revenue <i>W</i>_<i>F</i> is performed by comparing the difference between current and previous values of <i>W</i>_<i>F</i>. If the difference is less than a predefined threshold, the iterative procedure may be defined as being converged to an estimate for the optimum value for <i>W</i>_<i>F</i><i>.</i> If <i>W</i> is less than the predetermined threshold, at step <b>1008</b> the current values of <i>W</i>_<i>F</i> and the current estimates of <i>χ</i>_<i>sr</i> are provided as the optimum values of <i>W</i>_<i>F</i> and <i>χ</i>_<i>sr</i>. The predefined threshold may be determined off-line through network simulation or other methods known in the art. Otherwise, the procedure is iterated, by returning to step <b>1004</b>, using the current estimates of <i>χ</i>_<i>sr</i> as input values.

At step <b>1004</b> of FIG. 10, the performance of routing and network sensitivities with respect to maximized revenue <i>W</i>_<i>F</i> are determined by solving the linear programming problem, as given by equation (10) with the constraints of equation (11) and equation (12):<maths id="math0015" num=""><img file="EP1035751A2_D0017.tif" /></maths> In equation (10), equation (11), and equation (12), the value <i>χ</i>_<i>sr</i> ≥ 0 for all <i>s</i> and <i>r</i>, and <maths id="math0016" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext>ρ</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1035751A2_D0018.tif" /></maths>_<i>s</i>σ is the average (median or mean) traffic demand. As would be apparent to one skilled in the art, <i>W</i> ≤ <i>W</i>_<i>F</i>, where <i>W</i>_<i>F</i> is network revenue according to the solution of the linear programming problem, and <i>W</i> is the network revenue as determined from equation (2).

Linear programming techniques are well known in the art, and simplex-based or interior point-based techniques, for example, may be employed for a solution for the present invention. For example, simplex-based techniques are described in David G. Luenberger, Linear and Nonlinear Programming; Addison-Wesley, 1984. Interior point-based techniques are described in N.K. Karmarkar and KG. Ramakrishnan, Computational results of an interior point algorithm for large scale linear programming, <u>Mathematical Programming</u> 52 (1991) 555-586.

The network sensitivities may preferably be defined as the respective derivatives of network revenue with respect to the offered traffic rates <i>χ</i>_<i>sr</i> of service type <i>s</i> on route <i>r</i>. Solving the linear programming problem for network performance with respect to maximized revenue <i>W</i> also provides the values for the network sensitivities. Procedures known in the art may be employed to derive from the offered traffic rates and network sensitivities a measure of the desired bandwidth utilization for each link of each service route. The desired bandwidth utilization may then be employed to determine nominal allocations of bandwidth for each packet flow, or packet flow, to each link of each service route.

While the exemplary embodiments of the present invention have been described with respect to methods, the present invention is not so limited. As would be apparent to one skilled in the art, various functions may also be implemented in the circuits or a combination of circuits and in digital domain as processing steps in a software program of, for example, a digital signal processor, micro-controller or general purpose computer.

It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the scope of the invention as expressed in the following claims.