Patent Description:
Communication networks sometimes comprise ring configurations. For example, some networks comprise Resilient Packet Ring (RPR) configurations, as defined by the IEEE <NUM> working group. Applicable standards and additional details regarding RPR network configurations are available at www.

In some cases, connections are established over rings using tunneled protocols such as the Multiprotocol Label Switching (MPLS) protocol. MPLS is described in detail by<NPL>. This RFC, as well as other IETF RFCs cited hereinbelow, is available at www. MPLS is also described by <NPL>).

MPLS defines a label distribution protocol (LDP) by which one LSR informs another of the meaning of labels used to forward traffic between and through them. An extension of LDP for setting up constraint-based label switched paths (CR-LSPs) is referred to as CR-LDP and is defined by <NPL>. CR-LDP provides support for constraint-based routing of traffic across the routed network. LSPs can be set-up based on explicit route constraints, quality of service (QoS) constraints and other constraints.

Another protocol used for setting up MPLS tunnels is RSVP-TE, which is described by<NPL>. RSVP-TE extends the well-known Resource Reservation Protocol (RSVP), allowing the establishment of explicitly-routed LSPs using RSVP as a signaling protocol. RSVP itself is described by <NPL>).

In some applications, network elements allocate resources such as bandwidth to the services they provide. For example, the IETF has proposed the Integrated Services (IntServ) protocol architecture as a framework for allocating different levels of Quality of Service (QoS) to different services. IntServ is described by Braden et al. , in <NPL>).

Document <CIT> discloses a method of bandwidth management in a multiservice connection-oriented network which uses one or more overlooking factors and one or more overbooking models.

<FIG> is a block diagram that schematically illustrates a communication network <NUM>, in accordance with an embodiment of the present invention. Network <NUM> comprises multiple network nodes <NUM>. The network nodes may comprise, for example, layer <NUM> switches, layer <NUM> routers, bridges, concentrators, aggregators and add/drop multiplexers (ADM). Nodes <NUM> are connected by network links, referred to as segments <NUM>, which may comprise optical fiber links or any other suitable communication medium.

In the exemplary configuration of <FIG>, four network nodes denoted A, B, C and D are arranged in a ring configuration <NUM>, such as a resilient packet ring (RPR) configuration as defined in the IEEE <NUM> standard cited above. Ring <NUM> comprises two ringlets, namely a clockwise (CW) ringlet <NUM> and a counterclockwise (CCW) ringlet <NUM>. Segments <NUM> that belong to ring <NUM> are referred to as ring segments.

A connection <NUM> has been previously defined via network <NUM> and in particular via ring <NUM>. In the present example, connection <NUM> comprises a <NUM> Mbps connection (i.e., requiring a <NUM> Mbps bandwidth allocation in the segments along its route). The route of connection <NUM> enters ring <NUM> at node A and runs through clockwise ringlet <NUM> to node B. At node B the route leaves the ring and terminates at node E, which is located outside of ring <NUM>.

Now consider a new <NUM> Mbps connection, which is to be established through network <NUM>. Assume the new connection is required to enter ring <NUM> at node A, leave the ring at node C and terminate at node E. There exist two alternative routes for such a connection, corresponding to the two ringlets of ring <NUM>. A first candidate route <NUM> enters ring <NUM> at node A and follows clockwise ringlet <NUM>, traversing nodes B and C. At node C, candidate route <NUM> leaves the ring and terminates at node E. A second candidate route <NUM> enters ring <NUM> at node A and follows counterclockwise ringlet <NUM>, traversing nodes D and C. At node C, candidate route <NUM> leaves ring <NUM> and terminates at node E.

Connection <NUM>, as well as the new connection and the other connections described hereinbelow, may comprise MPLS label-switched paths. (LSP), or MPLS tunnels, in accordance with the MPLS tunnel creation protocols cited above. Alternatively, the connections may be defined using any other suitable communication protocol, such as ATM tunnel creation protocols.

In some cases, the new connection may be allowed to share its bandwidth allocation with existing connection <NUM>. For example, the new connection may be set up to protect the existing connection against failure of a node or segment along its route. In other cases, bandwidth may be allocated to connections with a certain degree of oversubscription. In other words, shared bandwidth may be allocated simultaneously to two or more connections, assuming that not all of these connections will actually use all of the allocated bandwidth simultaneously. Alternatively or additionally, connections may be defined as being allowed to share their bandwidth allocations for any other reason or purpose. In the exemplary configuration of <FIG>, it is assumed that the new connection may share its <NUM> Mbps bandwidth allocation in the segments along its route with the <NUM> Mbps bandwidth allocation of existing connection <NUM>.

Some known routing protocols, such as the Open Shortest Path First - Traffic Engineering (OSPF-TE) or the Intermediate System to Intermediate System - Traffic Engineering (IS-IS-TE) protocols, typically select routes for connections based on criteria such as minimum delay, minimum number of segments (hops), minimum cost and average or maximum available bandwidth. These known protocols generally do not take into account dependencies between the newly-established connection and previously-existing connections, such as the ability to share bandwidth allocation between the connections. Some known reservation protocols, such as RSVP-TE and LDP cited above, also do not enable sharing the bandwidth allocation among different connections.

The methods and systems described hereinbelow select one of the two candidate routes for establishing the new connection, so as to optimize the bandwidth allocation in ring <NUM>. Unlike the known routing protocols noted above, these methods and systems take into account the ability to share bandwidth between the new connection and existing connections that traverse ring <NUM>. In some embodiments, these methods and systems select a preferred route that achieves the smallest bandwidth allocation, taking into account bandwidth sharing. Thus, in the example shown in <FIG>, route <NUM> will be selected. In contrast, algorithms and protocols known in the art may select route <NUM>, because more bandwidth is available on the segments of this route, without regard to sharing considerations. Details of the process of route selection based on bandwidth sharing are explained below with reference to <FIG>. As a result of bandwidth sharing, the capacity of ring <NUM> is significantly improved, enabling it to deliver more bandwidth at a given QoS or to deliver higher QoS at a given capacity.

In general, the bandwidth-sharing connections through ring <NUM> may have similar or different bandwidths. The connections may originate and terminate at the same nodes or at different nodes, either within or outside ring <NUM>.

In the context of the present patent application and in the claims, the term "bandwidth" is used to refer to allocation of network capacity in accordance with any allocation scheme. Thus, allocated bandwidth may comprise, for example, guaranteed bandwidth (also referred to as committed information rate, or CIR), average bandwidth and/or peak bandwidth (also referred to as peak information rate, or PIR) provided only when available without hard guarantee.

<FIG> is a block diagram that schematically illustrates communication network <NUM>, in accordance with another embodiment of the present invention. In the exemplary configuration of <FIG>, ring <NUM> comprises six nodes <NUM> denoted A, B, C, D, E and F. A connection <NUM> is previously defined in the network. In the present example, connection <NUM> comprises a <NUM> Gbps connection (i.e., requiring a <NUM> Gbps bandwidth allocation in the segments along its route). The route of connection <NUM> enters ring <NUM> at node A, follows counterclockwise ringlet <NUM> through nodes F, E and D and leaves ring <NUM> at node C.

Consider another <NUM> Gbps connection, which is to be established through network <NUM>. Assume the new connection is required to enter ring <NUM> at node A and leave at node C, and may share its bandwidth allocation with the existing connection <NUM>. There exist two alternative routes for establishing the new connection. A first candidate route <NUM> follows the same route as the route of connection <NUM> via counterclockwise ringlet <NUM>, traversing nodes A, F, E, D and C. A second candidate route <NUM> follows clockwise ringlet <NUM>, traversing nodes A, B and C. As will be shown below, the disclosed methods and systems typically select route <NUM> so as to optimize the bandwidth allocation in nodes <NUM> of ring <NUM> based on bandwidth sharing.

The network configurations of <FIG> above are exemplary configurations, shown purely for the sake of conceptual clarity. The methods and systems described herein can be used in other ring configurations, such as, for example, the Synchronous Optical Network (SONET) Bidirectional Line Switch Ring (BLSR) configuration. In general, although the embodiments described herein mainly address bandwidth sharing over rings, the disclosed methods and systems are in no way limited to ring configurations, and can be used to establish connections in any other suitable network configuration that includes multiple network nodes and segments.

<FIG> is a block diagram that schematically illustrates details of network node <NUM>, in accordance with an embodiment of the present invention. Node <NUM> comprises a processor <NUM>, which performs the various processing functions of the node, and a network interface <NUM>, which communicates with other nodes <NUM> in network <NUM>.

In some embodiments, when two or more nodes <NUM> are arranged in a ring configuration (such as ring <NUM> in <FIG> above) processor <NUM> of one of these nodes comprises a ring-level connection admission control (CAC) module <NUM>, also referred to as a centralized CAC (CCAC) module. The CCAC module is responsible for performing ring-level resource allocation functions for the ring segments of ring <NUM>.

Ring-level CAC functions include, for example, verifying that sufficient bandwidth is available in the ring segments to support a new connection at the desired quality of service, and performing bandwidth reservations for such connections in the nodes and segments belonging to the ring. For the sake of clarity, in the description that follows the CCAC module responsible for performing CAC functions for the nodes and segments belonging to ring <NUM> will be referred to as the CCAC module of ring <NUM>.

Typically, processor <NUM> comprises a general-purpose computer, which is programmed in software to carry out the functions described herein. The software may be downloaded to the computer in electronic form, over a network, for example, or it may alternatively be supplied to the computer on tangible media, such as CD-ROM. Further alternatively, processor <NUM> may be implemented using a combination of hardware and software elements.

<FIG> is a flow chart that schematically illustrates a method for establishing a connection, in accordance with an embodiment of the present invention. The method is typically carried out by CCAC module <NUM> of ring <NUM>. The method begins with CCAC module <NUM> initiating the establishment of a new connection, at a connection initiation step <NUM>.

The CCAC module checks whether the new connection may share its bandwidth allocation with any of the existing connections that traverse ring <NUM>, at a sharing checking step <NUM>. In some embodiments, CCAC module <NUM> accepts an a-priori sharing definition, which defines connections traversing ring <NUM> that may share bandwidth allocations. Alternatively, the set-up procedure of the new connection may comprise a sharing definition stating other connections with which the new connection can share its bandwidth allocation.

In some embodiments, the sharing definition is distributed to nodes <NUM> using a signaling or reservation protocol, such as RSVP-TE and LDP cited above. The sharing definition is typically defined by an operator, such as a network administrator, as part of the network design. An exemplary method of defining the sharing of network resources and distributing the sharing definition to the network nodes is described in a <CIT>, which is assigned to the assignee of the present patent application and whose disclosure is incorporated herein by reference.

If the sharing definition states that the new connection may share its bandwidth allocation with at least one of the existing connections, CCAC module <NUM> determines which of the two candidate routes (i.e., the routes traversing clockwise ringlet <NUM> or counterclockwise ringlet <NUM> of ring <NUM>) is to be used for the new connection. For each of the two ringlets, CCAC module <NUM> calculates the cumulative additional bandwidth reservation that would be allocated in the ring segments of ring <NUM> to the new connection, at a reservation calculation step <NUM>. In some embodiments, prior to carrying out step <NUM>, CCAC module <NUM> verifies that both ringlets have sufficient available bandwidth to support the new connection. If only one of the ringlets has sufficient bandwidth, this ringlet is selected by default.

In some embodiments, the cumulative additional bandwidth reservation is given by: <MAT> <MAT> wherein ΔBWCW and ΔBWCCW denote the cumulative additional bandwidths on the clockwise and counter-clockwise ringlets, respectively.

The summation is performed over all ring segments S of the ringlet in question that belong to the candidate route traversing this ringlet. <MAT> denotes the bandwidth allocated in ring segment S to all connections including the new connection, taking in account bandwidth sharing, if the new connection were set up via the ringlet in question. <MAT> denotes the bandwidth allocated in ring segment S to all previously-existing connections (excluding the new connection). Thus, the term <MAT> gives the additional bandwidth reservation for ring segment S.

When calculating ΔBWCW and ΔBWCCW, CCAC module <NUM> considers only those connections that share their bandwidth with the new connection. In each ring segment, the CCAC module calculates the difference between the bandwidth allocated to these connections with and without the new connection. Parameter ΔBWCW accumulates the extra bandwidth that would be allocated to the new connection in the ring segments of clockwise ringlet <NUM>, if the new connection were to be established via this ringlet. Similarly, ΔBWCCW accumulates the extra bandwidth that would be allocated to the new connection in the ring segments of counterclockwise ringlet <NUM>. In particular, ΔBWCW and ΔBWCCW take into consideration that the new connection may share its bandwidth with at least one of the existing connections through ring <NUM>.

CCAC module <NUM> compares the cumulative additional bandwidth reservation values of the two ringlets, at a ringlet comparison step <NUM>. If the two values differ, CCAC module <NUM> selects the candidate route traversing the ringlet having the lower ΔBW value as a preferred route for establishing the new connection, at a ringlet selection step <NUM>. For example, ΔBWCW<ΔBWCCW means that the total extra bandwidth to be allocated due to the new connection is smaller in CW ringlet <NUM> than in CCW ringlet <NUM>, and vice versa. In other words, a ringlet in which less bandwidth is consumed, taking into account bandwidth sharing, will have a lower ΔBW value.

If the outcome of ringlet comparison step <NUM> above is that ΔBWCW=ΔBWCCW, the method reverts to a lower priority selection method, at a next priority selection step <NUM>. The method also reverts to step <NUM> from sharing checking step <NUM> above, if the new connection cannot share its bandwidth with any of the other connections.

The lower priority selection method may comprise any suitable method for choosing whether the preferred route for the new connection through ring <NUM> traverses CW ringlet <NUM> or CCW ringlet <NUM>. For example, the lower priority selection method may maximize the average available bandwidth between the source and destination nodes of the new connection. The lower priority selection method may or may not take into consideration bandwidth sharing between the connections. In some embodiments, two or more lower priority selection methods can be used, in which case the method loops through steps <NUM> and <NUM> until a preferred route is selected.

Returning to the exemplary network configuration of <FIG> above, applying the method of <FIG> would provide the following results: <MAT> <MAT> wherein ΔBWX→Y denotes the additional bandwidth that should be allocated to the new connection in the segment connecting node X to node Y, taking into account the ability to share bandwidth with the existing connection.

Therefore, candidate route <NUM> traversing CW ringlet <NUM> will be selected as the preferred route for the new connection that minimizes the consumed bandwidth. By contrast, methods that attempt to balance the bandwidth usage of the CW and CCW ringlets without considering bandwidth sharing would have chosen candidate route <NUM> instead, causing more bandwidth to be allocated.

In the exemplary network configuration of <FIG> above, applying the method of <FIG> would provide the following results: <MAT> <MAT>.

Therefore, in this case candidate route <NUM> traversing CCW ringlet <NUM> will be selected as the preferred route for the new connection that minimizes the consumed bandwidth. By contrast, methods that attempt to maximize available bandwidth or to minimize the number or segments without considering bandwidth sharing would have chosen candidate route <NUM> instead, causing more bandwidth to be allocated.

Although the embodiments described herein mainly address route selection based on bandwidth sharing, the principles of the present invention can be used for selecting routes by considering the sharing of other network resources used to support and process connections. For example, shared resources may comprise resources of network nodes, such as memory space and ports. Additionally or alternatively to addressing ring configurations, the methods and systems described herein can be used to select routes in any suitable network configuration.

Further additionally or alternatively, the methods described herein can be used in conjunction with known routing protocols, which normally do not take bandwidth sharing into account. For example, in some network configurations network nodes report available bandwidth in network segments using a known layer <NUM> protocol such as OSPF-TE or IS-IS-TE. The reported bandwidth is then used to make routing decisions. In some embodiments, the network nodes can calculate and report the available bandwidth using the methods described hereinbelow, taking into consideration bandwidth sharing among connections. Thus, the resulting routing decisions will implicitly depend on bandwidth sharing, enabling better use of network resources. Similarly, the methods and systems described herein can be used to enhance other bandwidth-related routing protocols by taking into consideration bandwidth sharing among connections.

It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and sub-combinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.

Claim 1:
A method for optimizing bandwidth allocation of carrying a data stream (<NUM>) that is associated with a required bandwidth allocation and is associated with a bandwidth sharing definition that defines the bandwidth sharing of the data stream with allocated bandwidths (<NUM>) over a network (<NUM>), the method comprising:
defining a first path (<NUM>) from a first node (A, <NUM>) to a second node (E, <NUM>) in the network (<NUM>), the first path comprises at least a first (<NUM>, A-B) segment that is associated with a first allocated bandwidths;
defining a second path (<NUM>) from the first node to the second node in the network, the second path comprises at least a second (<NUM>, A-D) segment that is associated with a second allocated bandwidths;
the method further comprising:
calculating (<NUM>) a first additional allocation bandwidth required for carrying the data stream over the first segment based on the first allocated bandwidth according to the bandwidth sharing definition;
calculating (<NUM>) a second additional allocation bandwidth required for carrying the data stream over the second segment based on the second allocated bandwidth according to the bandwidth sharing definition;
selecting (<NUM>) the first or second path in response to comparing (<NUM>) the first additional allocation bandwidth to the second additional allocation bandwidth; and
transporting the data stream (<NUM>, <NUM>) over the selected path,
wherein the first or second node comprises, or is part of, a Layer-<NUM> switch, a Layer-<NUM> router, a bridge, a concentrator, an aggregator, or an Add/Drop Multiplexer, ADM.