Method and system for sharing reserved bandwidth between several dependent connections in high speed packet switching networks

[0005] The present invention relates to bandwidth reservation in high speed packet networks and more particularly to a method and system for sharing reserved bandwidth between several virtual logical connections issuing from a same port attaching external devices.

[0006] HIGH SPEED PACKET SWITCHING NETWORKS

[0007] Data transmission is now evolving with a specific focus on applications and by integrating a fundamental shift in the customer traffic profile. Driven by the growth of workstations, the local area networks interconnection, the distributed processing between workstations and super computers, the new applications and the integration of various and often conflicting structures—hierarchical versus peer to peer, wide versus local area networks, voice versus data—the data profile has become more bandwidth consuming, bursting, non-deterministic and requires more connectivity. Based on the above, there is strong requirement for supporting distributed computing applications across high speed networks that can carry local area network communications, voice, video and traffic among channel attached hosts, business, engineering workstations, terminals, and small to intermediate file servers. This vision of a high speed multi-protocol network is the driver for the emergence of fast packet switching networks architectures in which data, voice, and video information is digitally encoded, chopped into small packets and transmitted through a common set of nodes and links.

[0008] An efficient transport of mixed traffic streams on very high speed lines means for these new network architecture a set of requirements in term of performance and resource consumption which can be summarized as follows:

[0009] a very high throughput and a very short packet processing time.

[0010] a very large flexibility to support a wide range of connectivity options,

[0011] an efficient flow and congestion control.

[0012] THROUGHPUT AND PROCESSING TIME

[0013] One of the key requirement of high speed packet switching networks is to reduce the end to end delay in order to satisfy real-time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes and the fundamental challenge for high speed networks is to minimize the processing time and to take full advantage of the high speed/low error rate technologies, most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end to end basis. The flow control and particularly the path selection and bandwidth management processes are managed by the access points of the network which reduces both the awareness and the function of the intermediate nodes.

[0014] CONNECTIVITY

[0015] In high speed networks, the nodes must provide a total connectivity. This includes attachment of the user's devices, regardless of vendor or protocol, and the ability to have the end user communicated with any other device. The network must support any type of traffic including data, voice, video, fax, graphic or image. Nodes must be able to take advantage of all common carrier facilities and to be adaptable to a plurality of protocols. All needed conversions must be automatic and transparent to the end user.

[0016] CONGESTION AND FLOW CONTROL

[0017] Communication networks have at their disposal limited resources to ensure an efficient packets transmission. An efficient bandwidth management is essential to take full advantage of a high speed network. While transmission costs per byte continue to drop year after year, transmission costs are likely to continue to represent the major expense of operating future telecommunication networks as the demand for bandwidth increases. Thus considerable efforts have been spent on designing flow and congestion control processes, bandwidth reservation mechanisms, routing algorithms to manage the network bandwidth. An ideal network should be able to transmit an useful traffic directly proportional to the traffic offered to the network and this as far as the maximum transmission capacity is reached. Beyond this limit, the network should operate at its maximum capacity whatever the demand is.

[0018] DEPENDENT CONNECTIONS

[0019] Private Network (PN) and Value-Added Network (VAN) service providers usually build their networks upon carrier transmission facilities. The expense for carrier transmission facilities represents an important part (about 30% to 60%) of the PN's or VAN's total operating expense. As such, their profits are directly related to their ability to minimize monthly transmission expenses while continually meeting their customers' end-to-end communications needs. Nodal equipment that can utilize the transmission facilities more efficiently than traditional carrier systems are typically selected by PNs and VANs.

[0020] Today, the replacement of traditional Time Division Multiplex (TDM) equipment by high speed packet switching equipment has significantly reduced the amount of transmission facilities needed in a Private Network (PN) or in a Value-Added Network (VAN). But much like TDM networks, packet switching networks approach falls short of reducing the amount of transmission facilities (transmission trunks) required in the backbone network. The reason for this is that most packet switching network architectures assume that all incoming traffic streams are “independent” with respect to each other. That is, any customer device attached to the network can provide incoming traffic to the network at any instant of time. This is not true for logical virtual connections as in the case of Frame Relay (FR), Local Area Network (LAN), or Asynchronous Transfer Mode (ATM) traffic. In fact, the logical connections of a FR, LAN or ATM attached device must consider the traffic sources from all logical virtual connections established on a given physical port as “dependent”. When a logical virtual connection is bursting a traffic stream, no other logical virtual connection can burst at the same time.

[0021] A network architecture such as the NBBS architecture described in IBM's publication entitled “Networking Broadband Services (NBBS)—Architecture Tutorial” IBM ITSC, June 1995 GG24-4486-00, reserves for virtual Frame Relay (FR) connections more bandwidth than necessary on the backbone network. This occurs because NBBS considers each Data Link Connection Identifier (DLCI) (refer to Frame Relay core aspects ANSI T1.618-1991 and ITU-T Q.922 Annex A) as an independent traffic source, and reserves bandwidth on the backbone network accordingly. FIG. 4 illustrates virtual Frame Relay/ATM (FR/ATM) connections between four nodes, named A, B, C, and D. Digital Terminal Equipment are connected to ports in these nodes by means of access links. From the Frame Relay/ATM port in origin node A, three virtual logical connections are established respectively towards destination ports B, C and D. Assuming in this example that the traffic is the same for each connection:

[0022] R (Access Rate)=2 Mbps,

[0023] CIR (Committed Information Rate)=300 kbps,

[0024] B_c(Burst Committed)=4 kbytes

[0025] the bandwidth reserved on a trunk with a multiplexing buffer of 64 kbytes in order to guarantee a packet loss probability of ε=5×10⁻⁸, is approximately 700 kbps for each connection.

[0026] The bandwidth reserved by the NBBS architecture on a trunk to support a connection is defined according to the following equation: $\hat{c}=R\frac{y-X+\sqrt{{\left[y-X\right]}^2+4X\rho y}}{2y}\simeq 700\mathrm{kbps}$

[0027] where: $\begin{array}{c}X=64000\mathrm{bytes}\times 8=512000\mathrm{bits}\\ \left(\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{buffer}\mathrm{where}\mathrm{packets}\mathrm{are}\mathrm{queued}\right),\\ b=\frac{B_c}{R}=\frac{4\mathrm{kbytes}\times 8}{2048\mathrm{kbps}}=0.16\mathrm{ms}\left(\mathrm{average}\mathrm{burstiness}\right),\\ y=\ln \left(1/ϵ\right)b\left(1-\rho \right)R,\mathrm{and}\\ \rho =\mathrm{CIR}/R=300\mathrm{kbps}\text{/}2048\mathrm{kbps}\simeq 0.15.\end{array}$

[0028] Therefore, the bandwidth reserved on each trunk is given in the table below:

[0029] This example shows that the total bandwidth that should be reserved for 3 connections on Trunk 1 is about 2100 kbps (3 connections at 700 kbps). The value is higher than the access rate (R=2 Mbps) of the physical port (FR/ATM port A) supporting these connections. This situation is clearly not acceptable. In the simple case where a physical port is fully loaded with 7 connections (7×300 kbps=2 Mbps) and where all the connections issuing from said port are transmitted over a single trunk (Trunk 1), the bandwidth requirement is about 4.9 Mbps (7×700 kbps), while it is clear that the 2 Mbps stream produced by said port can be transmitted over a 2 Mbps trunk. Again, this occurs because NBBS considers each connection as an independent traffic source and supposes that all connections can be bursty at the same time. Considering this worst case, NBBS reserves 4.9 Mbps to be sure to be able to transmit 2 Mbps.

[0030] NON PUBLISHED U.S. PATENT APPLICATION SER. NO. 97,131

[0031] Non published U.S. patent application Ser. No 97,131 (IBM's reference FR 9 95 035) entitled “Method and System for Sharing Reserved Bandwidth Between Several Dependent Connections in High Speed Packet Switching Networks” (Galand et al.) discloses a Dependent Connection Bandwidth Management method and system for taking advantage of the property of dependent virtual logical connections in a packet switching communication network comprising a plurality of nodes interconnected with transmission trunks. More particularly, the object of this application is to share the reserved bandwidth between several connections issuing from a same physical access port. An aggregate bandwidth is reserved for all connections issuing from the same physical port, this aggregate bandwidth is defined as being less than the sum of the bandwidth reserved for each connection considered individually. In a network where the bandwidth reserved for an individual connection is equal to the equivalent capacity of the connection, the aggregate bandwidth reserved for all dependent connections is defined as a function of:

[0032] the mean bit rate of the aggregation of connections issued from said port, and

[0033] the mean burst duration of the aggregation of connections issued from said port.

[0034] The Dependent Connection Bandwidth Management process as described in the specifications is based on:

[0035] 1. an accounting per port of all connections established on every link in the network.

[0036] 2. a modification of the Path Selection algorithm in access nodes,

[0037] 3. an insertion of additional fields in the connection set-up message, and

[0038] 4. a modification of the Transit Connection Manager (TCM) algorithm within Transit nodes.

[0039] This solution reduces the bandwidth required for the dependent connections in the backbone network, while still guaranteeing an end-to-end quality-of-service. However, this solution is complex to implement and resource consuming because based on a set of algorithms implemented in both access nodes (in particular in the Path Selection), and transit nodes (in the Transit Connection Managers (TCM)).

[0040] The object of the present application is to provide an improved method and system for saving bandwidth on links taking advantage of the property of dependent connections while limiting the resources required for establishing connections in both access and transit nodes.

[0041] It is another object of the present application to reduce the processing time necessary to establish connections and in particular the time for selecting a routing path. It is another object of the present application to make easier the migration of existing. networks and the coexistence of the present invention with other networks architectures.

[0042] According to the present invention dependent connections are managed:

[0043] independently of the Path Selection algorithm, and

[0044] only in access nodes.

[0045] At each request for establishing a connection i from an origin node to a destination node, the dependent connection management process:

[0046] selects for connection i a routing path comprising one or a plurality of links from the origin node to the destination node;

[0047] identifies on the selected path all consecutive links starting from the origin node and shared with another connection issuing from the same physical port;

[0048] reserves on each link of these identified consecutive links an aggregate bandwidth for all connections issuing from the same physical port, said aggregate bandwidth being less than the sum of the bandwidth reserved for each connection considered individually.

[0049] Two tables are defined for each port p:

[0050] a Dependent Connection Table DCT_pcomprising for each link in the network, information required to manage the bandwidth and the dependency of connections issuing from the port;

[0051] a Path Table PT_pwith the links comprised in the selected routing path of each connection issuing from the port.

[0052] FIG. 1 describes the bandwidth reservation process.

[0053] FIG. 2 shows a typical model of high speed packet switching network including the nodes claimed in the present invention.

[0054] FIG. 3 describes a high speed Routing Point according to the present invention.

[0055] FIG. 4 shows a typical Frame Relay/ATM network.

[0056] FIG. 5 describes the Topology Database structure.

[0057] FIG. 6 shows the link characteristics stored in the Topology Database.

[0058] FIG. 7 shows the Path Selection and the connection set-up process according to prior art.

[0059] FIG. 8 shows the Path Selection and the connection set-up process according to U.S. patent application Ser. No. 97131 (IBM's reference FR 9 95 035).

[0060] FIG. 9 shows the Path Selection and the connection set-up process for dependent connections according to the present invention.

[0061] FIG. 10 is a general view of a high packet switching network showing in particular 5 dependent connections issued from the same port p at node A.

[0062] FIG. 11 shows the Path Table structure at node A for port p according to the present invention.

[0063] FIG. 12 is a flow chart of the Path Matching algorithm according to the present invention.

[0064] FIG. 13 is a flow chart of the Connection Aggregation algorithm according to the present invention.

[0065] HIGH SPEED COMMUNICATIONS

[0066] As illustrated in FIG. 2, a typical model of communication system is made of several user networks (212) communicating through a high performance network (200) using private lines, carrier provided services, or public data networks. Each user network can be described as a set of communication processors and links (211) interconnecting large computers used as enterprise servers (213), user groups using workstations or personal computers attached on LAN (Local Area Networks 214), applications servers (215), PBX (Private Branch eXchange 216) or video servers (217). These user networks, spread in different establishments, need to be interconnected through wide area transport facilities and different approaches can be used for organizing the data transfer. Some architectures involve the checking for data integrity at each network node, thus slowing down the transmission. Others are essentially looking for a high speed data transfer. To that end the transmission, routing and switching techniques within the nodes are optimized to process the flowing packets toward their final destination at the highest possible rate. The present invention belongs essentially to the latter category and more particularly to the fast packet switching network architecture detailed in the following paragraphs.

[0067] HIGH PERFORMANCE PACKET SWITCHING NETWORKS

[0068] The general view in FIG. 2 shows a fast packet switching transmission system comprising eight nodes (201 to 208) each node being interconnected by means of high speed communication lines called Trunks (209). The access (210) to the high speed network by the users is realized through Access Nodes (202 to 205) located at the periphery. These Access Nodes comprise one or more Ports, each one providing an access point for attaching external devices supporting standard interfaces to the network and performing the conversions required to transport the users data flow across the network from and to other external devices. As example, the Access Node (202) interfaces respectively a Private Branch exchange (PBX), an application server and a hub through three Ports and communicates through the network by means of the adjacent Transit Nodes (201), (205) and (208).

[0069] SWITCHING NODES

[0070] Each network node (201 to 208) includes a Routing Point where the incoming data packets are selectively routed on the outgoing Trunks towards the neighboring Transit Nodes. Such routing decisions are made according to the information contained in the header of the data packets. In addition to the basic packet routing function, the network nodes provide ancillary services such as:

[0071] the determination of routing paths for packets originated in the node,

[0072] directory services like retrieving and updating information about network users and resources,

[0073] the maintaining of a consistent view of the physical network topology, including link utilization information, and

[0074] the reservation of resources at access points of the network.

[0075] According to the present invention, these ancillary services include:

[0076] the storage within the node of alternate paths,

[0077] the updating of these paths.

[0078] Each Port is connected to a plurality of user processing equipment, each user equipment comprising either a source of digital data to be transmitted to another user system, or a data sink for consuming digital data received from another user system, or, typically, both. The interpretation of the users protocols, the translation of the users data into packets formatted appropriately for their transmission on the packet network (200) and the generation of a header to route these packets are executed by an Access Agent running in the Port. This header is made of Control, Routing and Redundancy Check Fields.

[0079] The Routing Fields contain all the information necessary to route the packet through the network (200) to the destination node to which it is addressed. These fields can take several formats depending on the routing mode specified (connection oriented or connectionless routing mode . . . ).

[0080] The Control Fields include, among other things, an encoded identification of the protocol to be used for interpreting the Routing Fields.

[0081] The Redundancy Check Fields are used to check for errors in the header itself. If an error is detected, the packet is discarded.

[0082] ROUTING POINTS

[0083] FIG. 3 shows a general block diagram of a typical Routing Point (300) such as it can be found in the network nodes (201 to 208) illustrated in FIG. 2. A Routing Point comprises a high speed packet Switch (302) onto which packets arriving at the Routing Point are entered. Such packets are received:

[0084] from other nodes over high speed transmission links (303) via Trunk Adapters (304).

[0085] from users via application adapters called Ports (301).

[0086] Using information in the packet header, the adapters (304, 301) determine which packets are to be routed by means of the Switch (302) towards a local user network (307) or towards a transmission link (303) leaving the node. The adapters (301 and 304) include queuing circuits for queuing packets prior to or subsequent to their launch on the Switch (302).

[0087] The Route Controller (305) calculates the optimum paths through the network (200) so as to satisfy a given set of quality-of-services specified by the user and to minimize the amount of network resources used to complete the communication path. Then, it builds the header of the packets generated in the Routing Point. The optimization criterion includes the number of intermediates nodes, the characteristics of the connection request, the capabilities and the utilisation of the links (Trunks) in the path, the number of intermediate nodes . . . The optimum route is stored in a Routing Database (308) for further reuse.

[0088] All the information necessary for the routing, about the nodes and transmission links connected to the nodes, are contained in a Network Topology Database (306). Under steady state condition, every Routing Point has the same view of the network. The network topology information is updated when new links are activated, new nodes added to the network, when links or nodes are dropped or when link loads change significantly. Such information is exchanged by means of control messages with all other Route Controllers to provide the up-to-date topological information needed for path selection (such database updates are carried on packets very similar to the data packets exchanged between end users of the network). The fact that the network topology is kept current in every node through continuous updates allows dynamic network reconfigurations without disrupting end users logical connections (sessions).

[0089] The incoming transmission links to the packet Routing Point may comprise links from external devices in the local user networks (210) or links (Trunks) from adjacent network nodes (209). In any case, the Routing Point operates in the same manner to receive each data packet and forward it on to another Routing Point is dictated by the information in the packet header. The fast packet switching network operates to enable a communication between any two end user applications without dedicating any transmission or node facilities to that communication path except for the duration of a single packet. In this way, the utilisation of the communication facilities of the packet network is optimized to carry significantly more traffic than would be possible with dedicated transmission links for each communication path.

[0090] NETWORK CONTROL FUNCTIONS

[0091] The Network Control Functions are those that control, allocate, and manage the resources of the physical network. Each Routing Point has a set of the foregoing functions in the Route Controller (305) and uses it to facilitate the establishment and the maintenance of the connections between users applications. The Network Control Functions include in particular:

[0092] Directory Services

[0093] for retrieving and maintaining information about network users and resources.

[0094] Bandwidth Management

[0095] for processing the bandwidth reservation and maintenance messages, and

[0096] for monitoring the current reservation levels on links.

[0097] Path Selection

[0098] for choosing the best path for each new connection considering the connection requirements and the current link utilisation levels.

[0099] Control Spanning Tree

[0100] for establishing and maintaining a routing tree among the network nodes,

[0101] for using it to distribute control information (in parallel) including link utilisation, and

[0102] for updating the Topology Database of the nodes with new network configurations or link/node failures.

[0103] Topology Update

[0104] for distributing and maintaining, using the Spanning Tree, information about the logical and physical network (including link utilization information) in every node.

[0105] Congestion Control

[0106] for enforcing the bandwidth reservation agreements between the network's users and the network which are established at the call set up time, and

[0107] for estimating actual bandwidth and for adjusting reservation if necessary during the life of the connection.

[0108] The Topology Database contains information about nodes, links, their properties, and the bandwidth allocation. The topology information is replicated in each node of the network. An algorithm guarantees the correctness of each node's Topology Database when links and nodes are added or deleted or when their characteristics change. The database comprises:

[0109] the physical topology of the network which includes static information like physical characteristics of nodes and links,

[0110] the state of nodes and links, and

[0111] the link utilisation which includes dynamic characteristics like current bandwidth (used and reserved), real-time measurements . . .

[0112] The general organisation of the Topology Database is shown in FIG. 5. To each resource in the network, nodes (501) or links (502), is associated an entry in the database. In particular, each link entry includes the following characteristics:

[0113] (503) The Link Physical Properties

[0114] transmission medium and speed,

[0115] routing mode supported,

[0116] maximum packet size,

[0117] link buffer capacity,

[0118] propagation delay,

[0119] bandwidth reservation supported . . .

[0120] (504) The Link State

[0121] on-line (link can accept user connections),

[0122] quiesce (link cannot accept additional user

[0123] connections, but existing connections continue),

[0124] off-line (link cannot accept user connections and existing connections are cancel led) . . .

[0125] (505) The Link Utilization:

[0126] real-time measurements,

[0127] reserved bandwidth, . . .

[0128] FIG. 6 shows in a table, some of the information stored in the Topology Database. Though all characteristics of the links are listed in each node, in the present application only a few will be described:

[0129] Total Capacity (bps) C

[0130] The Topology Database contains, for each link, its Total Capacity. The value C_krepresents the total bandwidth available on the link k between two nodes.

[0131] Reservable Fraction (%) rf

[0132] As might be expected, one of the critical characteristics of transmission links is the fraction of the link capacity effectively available. Links cannot be loaded up to a theoretical maximum load (bandwidth) for two reasons:

[0133] first, to set aside bandwidth for network control functions, and

[0134] secondly, to keep the loss probabilities and queueing delays low in the case of short term bandwidth violations by the different traffic sources.

[0135] The reservable fraction of a link rf is the effective percentage of the Total Capacity C_kthat can be reserved on the link k, to maintain a reasonable quality of transmission. If C_kis the Total Capacity of the link k, then R_k=rf×C_kis the Reservable Capacity of this link (Ĉ_k≦R_k≦C_k).

[0136] Note: For most network architectures, no more than 85% of the total bandwidth of a link C_kcan be explicitly reserved for user traffic (rf<0.85).

[0137] Total Reserved Equivalent Capacity (bps) Ĉ_R,k

[0138] For a connection i on a link k, the simplest way to provide low/no packet loss would be to reserve the entire bandwidth requested by the user. However, for bursty user traffic, this approach can waste a significant amount of bandwidth across the network. To save resources, the bandwidth amount actually reserved is equal to an “Equivalent Capacity” Ĉ_k,j, said Equivalent Capacity being a function of the source characteristics and of the network status. The bandwidth reservation falls somewhere between the average bandwidth required by the user and the maximum capacity of the connection.

[0139] The value ${\hat{C}}_{R,k}=\sum _{i=1}^N{\hat{c}}_{k,i}=\mathrm{sum}$

[0140] of the reserved Equivalent Capacities represents the total bandwidth reserved on the link k by N connections already established. If the difference between this already reserved link Equivalent Capacity Ĉ_R,kand the Total Reservable Capacity of the link rf×C_kis less than the bandwidth requested by a new reserved connection then the link cannot be selected. However, the link may be selected for a non-reserved connection where no explicit bandwidth reservation is needed.

[0141] Total Bandwidth used by Non-Reserved Traffic (bps) M_NR,k

[0142] The value M_NR,krepresents the total load or bandwidth currently used by non-reserved traffic as measured on the link k.

[0143] Total Capacity Used (bps) Ĉ_T,k

[0144] The Total Bandwidth Used Ĉ_T,kon the link k is computed by adding the total reserved bandwidth Ĉ_R,kand the measured bandwidth M_NR,kused by non-reserved traffic.

[0145] Maximum Packet Size (bytes) mps_k

[0146] mps_kis defined as the maximum packet size supported by the link k.

[0147] BANDWIDTH MANAGEMENT

[0148] Users are requiring different quality-of-services. In order to provide the various service levels, different types of network connections are established. A connection is defined as a path in the network between the origin access node and the destination access node representing respectively the source user and the target user. Networks connections can be classified as reserved or non-reserved. Reserved network connections require bandwidth to be allocated in advance along the chosen path.

[0149] Most of the high speed connections are established on a reserved path to guarantee the quality of service and the bandwidth requested by the user. This path across the network is computed by the origin node using information in its Topology Database including current link utilization. The origin node then sends a reservation request along the chosen path, and intermediate nodes (if allowing the reservation) then add this additionally reserved capacity to their total. These changes are reflected in topology broadcast updates sent by the intermediate nodes. Intermediate nodes need not to have an awareness of the status of each connection on their adjacent links. If an intermediate node does get too many packets, generally because of unanticipated burstiness, it simply discards them (the user can select a service that will recover from such discards).

[0150] Depending on the node type, the function of the Bandwidth Management is:

[0151] in the origin node,

[0152] to identify the best possible route according to the network status and the connection parameters including the connection priority,

[0153] to reserve at connection setup, the bandwidth required by the network connections and to maintain this bandwidth for the duration of the connection.

[0154] to reject the connection if resources needed to satisfy the request are not available in the network.

[0155] in a transit node,

[0156] to administer the bandwidth reservations on the links, and

[0157] according to the present invention to administer the bandwidth reservations on the links of the alternate paths.

[0158] BANDWIDTH RESERVATION

[0159] The connection set up and bandwidth reservation process, as shown in FIG. 1, comprises the following steps:

[0160] (101) a Connection Request is specified by the user via a set of parameters including origin and destination network address, and data flow characteristics (bit rate, burstiness).

[0161] (102) a Path Selection process determines a path and a set of connection requests, one for each link of the path, using parameters provided by the Topology Database.

[0162] (103) a Bandwidth Reservation process uses the connection requests to reserve bandwidth on each of the links of the path. This process involves exchange of information (109) between the origin (access) node (100), the transit nodes (107) on the path, and the destination node (108).

[0163] (104) Bandwidth Reservation replies from transit nodes and end node generate either a call acceptance or a call reject (110).

[0164] (105) a Link Metric Update process updates, in case of call acceptance, the modified link metrics. This information (111) is sent through the Control Spanning Tree to the Topology Database of each node in the network by means of a broadcast algorithm.

[0165] (106) a Congestion Control Set Up adjusts, if the call is accepted, the network connection characteristics.

[0166] The bandwidth reservation process is performed in the origin and destination nodes by Connection Agents (CA) and by Transit Connection Managers (TCMs) in the transit nodes along the chosen path.

[0167] PATH SELECTION

[0168] The purpose of the Path Selection process is to determine the best way to allocate network resources to connections both to guarantee that user quality of service requirements are satisfied and also to optimize the overall throughput of the network. The Path Selection process must supply to the requesting user a path over the network over which a point-to-point connection will be established, and some bandwidth will be reserved if needed. As shown in FIG. 12, the Path Selection algorithm uses as input parameters in one hand the user requirements and on the other hand the status of the network links and nodes as maintained in the Topology Database.

[0169] The Path Selection process takes place entirely within the node wherein the connection is requested. It makes use of the Topology Database and selects the “best path” based on each of the following criteria in order of importance:

[0170] Quality-of-Service:

[0171] The connection's quality-of-service requirements are to be satisfied throughout the life of the connection. There are a large number of variables that determine the performance of a network. However, the quality-of-service can be defined as the set of measurable quantities that describe the user's perception of the service offered by the network. Some of the quality-of service parameters are listed below:

[0172] connection set up delay,

[0173] connection blocking probability,

[0174] loss probability,

[0175] error probability,

[0176] end-to-end transit delay,

[0177] end-to-end delay variation,

[0178] . . .

[0179] Some of these quantities have an effect upon how paths are computed, for example the packet loss probability or the end-to-end transit delay: the sum of propagation delays along a computed path may not violate the end-to-end transit delay specifications.

[0180] Minimum Hop

[0181] The path shall consist of as few links as feasible to support the connection's quality of service requirements, thus minimizing the amount of network resources as well as processing costs to support the connection. The path computation is based on the links utilization at the time the connection is requested.

[0182] Load Balancing

[0183] Among a minimum hop path, a path with “lightly loaded” links is preferred over a path with “more heavily loaded” links based on the network conditions at the time of path selection. The load of a link depend of the customer criteria: it can be an increasing function of the total reserved bandwidth of the link, proportional to the amount of traffic actually measured on the link, . . . When the path load (sum of the load of the links over the selected path) is the preponderant criterion of selection, the path of lesser load is chosen.

[0184] Satisfying the first requirement is the key factor in path selection and the other two functions are used to optimize traffic through the network.

[0185] BANDWIDTH MANAGEMENT ACCORDING TO PRIOR ART

[0186] The bandwidth management of the NBBS (Networking BroadBand Services) architecture illustrated in FIG. 7 is described in the present specification as example of prior art. For simplicity, a single class of service is considered. However, it should be clear that the extension to multi-priorities is straightforward and is covered by NBBS (for more details about NBBS, refer to IBM's publication entitled “Networking Broadband Services (NBBS) Architecture Tutorial”—IBM ITSC June 1995 GG24-4486-00).

[0187] CONNECTION METRICS

[0188] Metrics are used to represent network connections with different characteristics. They are obtained from a model that captures the basic behavior of the data source associated with a connection. The behavior of any source can be modeled with a two state model: a source is either idle, generation no data, or active, transmitting data at its peak rate. The bit rate of a connection can therefore be represented by two states, namely: an idle state (transmitting at zero bit rate) and a burst state (transmitting at peak rate). A burst is defined to be a sequence of packets transmitted by the source into the network at its peak rate. The:

[0189] peak rate of a connection,

[0190] distribution of the idle period, and

[0191] distribution of burst length,

[0192] completely identify the traffic statistics of a connection, assuming the duration of burst and idle periods are exponentially distributed and are not correlated. In this two-state model, a connection i is defined by its metric c_i=(R_i, m_i, b_i), where

[0193] R_i(in bits per seconds) is the access bit rate (peak bandwidth),

[0194] m_i(in bits per seconds) is the average bit rate, and

[0195] b_i(in seconds) is the average burstiness (mean burst duration).

[0196] These three parameters are used to specify the bandwidth requirements for the network connection so that the appropriate path can be selected and sufficient bandwidth reserved. Additionally, these parameters are used by the Congestion Control function to monitor conformance of the network connection to its bandwidth reservation.

[0197] The variance of the bit rate is σ_i²=m_i(R_i−m_i).

[0198] The quantities m_iand σ_i²provide indications of the mean bandwidth requirement, in bits per second, of a network connection and the magnitude of fluctuations around this mean value. The quantity b gives an indication of the duration of transmission bursts generated by the source. For the same utilization, a large b indicates that the source alternates between long burst and idle periods. A small b indicates that data is generated in short alternating burst and idle periods. Two sources with identical mean and peak bit rates but different burst periods, have different impacts on the network. For example, a long burst will have a major impact on queueing points in the network.

[0199] EQUIVALENT CAPACITY

[0200] The Equivalent Capacity of a network connection c_i=(R_i, m_i, b_i) is defined as the minimum bandwidth needed on a link to support the connection assuming that no other connections are using the link. $\begin{array}{cc}{\hat{c}}_i=f\left(R_i,m_i,b_i,X,ϵ\right)=R_i\frac{y_i-X+\sqrt{{\left[y_i-X\right]}^2+4X{\rho }_i{y}_i}}{2y_i}& \left(1\right)\end{array}$

[0201] where:

[0202] X is the size of the buffer where packets are queued while waiting transmission on the trunk line. Large buffer sizes enable bursts of traffic to be handled without packet loss. However, large buffer sizes also enable a larger queueing delay; therefore, the buffer size is usually related to the delay priority associated with a network connection.

[0203] ε is the proportion of packets that can be lost due to the buffer overflowing. This proportion or packet loss ratio objective is dependent on the quality-of-service required by the network connection, and will generally be very small indeed (less than 10⁻⁶).

[0204] y_i=ln(1/ε)b_i(1−p_i)R_i, and

[0205] p_i=m_i/R_i.

[0206] In case of a continuous bit stream connection, p_i=1 (m_i=R_i), b_i=∞ and ĉ_i=R_i.

[0207] LINK BANDWIDTH MANAGEMENT

[0208] A Link Metric vector is a triplet representing the aggregation of all the connections i traversing a link k (in NBBS, several link metrics are defined, corresponding to the different delay priorities, but as mentioned, the simplified assumption of a single class of service per trunk is used). Link Metrics vectors are distributed to other nodes via Topology Database (TDB) update messages. The Equivalent Capacity Ĉ_kassociated with the aggregation of N_kconnections established on the link k, combines two characteristics of the traffic of the network:

[0209] The bandwidth needed by a single network connection considered separately, a function of its characteristics, system resources and desired quality-of-service.

[0210] The impact of statistical multiplexing when many network connections, possibly with different characteristics, are aggregated. $\begin{array}{cc}{L}_k=\left\{M_k=\sum _{i=1}^{N_k}{m}_i,S_k^2=\sum _{i=1}^{N_k}{\sigma }_i^2,{\hat{C}}_k^{\left(N_k\right)}=\sum _{i=1}^{N_k}{\hat{c}}_i\right\}{L}_k=\left\{\sum _{i=1}^{N_k}{m}_i,\sum _{i=1}^{N_k}{m}_i\left(R_i-m_i\right),\sum _{i=1}^{N_k}{\hat{c}}_i\right\}& \left(2\right)\end{array}$

[0211] where the index i runs over the N_kconnections already transported on the trunk.

[0212] Relation (2) can be written:

[0213] L_k={M_k,S_k²,Ĉ_k^(N)}  (3)

[0214] where: $M_k=\sum _{i=1}^{N_k}{m}_i\text{:}$

[0215] sum of the mean of bit rates=mean of the aggregate bit rate, $S_k^2=\sum _{i=1}^{N_k}{m}_i\left(R_i-m_i\right)\text{:}$

[0216] sum of the variances of the bit rates=variance of the aggregate bit rate, ${\hat{C}}_k^{\left(N_k\right)}=\sum _{i=1}^{N_k}{\hat{c}}_i$

[0217] sum of the individual Equivalent Capacities of all the N_kconnections established on the link k.

[0218] The current level of reservation of the link k is given by: $\begin{array}{cc}{\hat{C}}_k^1=\min \left\{\sum _{i=1}^{N_k}\left(m_i+\alpha {\sigma }_i\right),\sum _{i=1}^{N_k}{\hat{c}}_i\right\}=\min \left\{\left(M_k+\alpha S_k\right),{\hat{C}}_k^{\left(N_k\right)}\right\}& \left(4\right)\end{array}$

[0219] with:

[0220] α≅{square root over (2In 1/ε−In 2π)},

[0221] Equation (4) provides a reasonably accurate estimate of the capacity required to support a given set of network connections.

[0222] The first function (M_k+αS_k) relies on a Gaussian approximation to characterize the aggregate bit rates of all connections routed over a link k. This model capture the stationary behaviour of aggregate bit rate and provides a good estimate for cases where many connections have long bursts periods and relatively low utilization. In such cases, individual network connections often require close to their peak, while the stationary behavior of their aggregation indicates that much less is in fact needed. The Gaussian assumption, however implies that the model may be inaccurate when used with a small number of high peak rate network connections.

[0223] The second function (sum of the individual equivalent capacities obtained for equation (1)) captures the impact of source characteristics, in particular the duration of the burst period, on the required bandwidth. This result is substantial capacity savings when the duration of the burst period is small.

[0224] From equation (4), it is seen that the equivalent capacity can be easily updated as new connections are added or removed, provided that the total mean and variance of the bit rate and the sum of all individual equivalent capacities are kept.

[0225] PATH SELECTION

[0226] Bandwidth request messages for routing new connections (R_i, m_i, b_i) and updating the Link Metric vectors, contain a request vector defined by:

[0227] r_i=(m_i,σ_i²,ĉ_i)

[0228] Note: The access bit rate (peak bandwidth) R_iis derived from this request vector r_iby means of the expression:

[0229] R_i=m_i+σ_i²/m_i

[0230] A Path Selection algorithm—a variant of the Bellman-Ford algorithm in a preferred embodiment—is then executed. The algorithm screens the network links which are defined in the Topology Database (TDB). For each link examined as a candidate for being part of the path, the Path Selection:

[0231] 1. Computes the Equivalent Capacity ĉ_iof the connection i over this link using relation (1).

[0232] 2. Determines Whether the Connection is Multiplexable or not

[0233] The Part Selection computes t₁=C_k⁰−N×m_iand t₂=α²N×σ_i², where:

[0234] C_k⁰represents the link reservable bandwidth, and

[0235] N′ is a constant specifying the minimum number of connections needed by the Gaussian assumption.

[0236] 3. Estimates the Link Metric L′_kif the New Connection is to be Added

[0237] Two cases must be distinguished, depending on the potential impact of the network connection on the link; the need for these two cases arises from the form of the equation (4). More specifically, the assumption that the aggregate bit rate has a Gaussian distribution is valid only if a sufficient number of connections can be multiplexed on the link. For any given type of connection, this depends on both the connection characteristics and the total link bandwidth.

[0238] If t₁>0 and t₂<t₁², then the connection is multiplexable, and the Gaussian approximation is used:

[0239] L′_k=L_k+r_i=L_k+(m_i,σ_i²,ĉ_i)={M′_k,S′_k²,Ĉ′_k^(N+1)}  (5)

[0240] where addition is component-wise.

[0241] Else, the connection is not multiplexable, and the Equivalent Capacity must be reserved on the link:

[0242] L′_k=L_k+{tilde over (r)}_iL_k+(ĉ_i, 0,ĉ_i)={M′_k,S′_k²,Ĉ′_k^(N+1)}  (6)

[0243] Equation (6) simply states that network connections for which the Gaussian assumption does not hold are treated as constant bit rate connections (σ_i²=0) with rate equal to their equivalent capacity as given by equation (1). From the updated Link Metric vector, the new allocated equivalent bandwidth is easily computed using again equation (4).

[0244] 4. Checks the Link Eligibility

[0245] The ability of the link to handle the new connection is then checked. The bandwidth which would be reserved on the link after the new connection has been accepted on this link is equal to:

[0246] Ĉ_k²=min{(M′_k+α.S′_k),Ĉ′_k^(N+1)}  (7)

[0247] where the (M′_k, S′_k², Ĉ′_k^(N+1)) values denote the components of the Link Metrics as updated by relations (5) or (6). The link is able to handle the new connection if

[0248] Ĉ_k²≦C_k⁰  (8)

[0249] 5. Computes the Load Balancing Weight of the Link

[0250] If the link k is eligible, the link ability to support the new connection is estimated by the load balancing weight of the link: $\begin{array}{cc}{w}_k=\frac{C_k^0}{\left(C_k^0-{\hat{C}}_k^1\right)\left(C_k^0-{\hat{C}}_k^2\right)}& \left(9\right)\end{array}$

[0251] where:

[0252] Ĉ_k¹is computed from relation (4) and represents the bandwidth currently reserved on the link k not taking the requesting connection into account.

[0253] Ĉ_k²represents the bandwidth that will be reserved on the link k if the link is chosen to carry the requesting connection.

[0254] C_k⁰is the total capacity of the link k.

[0255] This Link Weight w_kis then used in the Path Selection algorithm to properly insure load balancing in the network.

[0256] CONNECTION ESTABLISHMENT

[0257] Once a path has been selected in the network, the Connection Agent (CA) in origin node prepares a connection set-up message and sends it over the path, with a copy to every Transit Connection Manager (TCM) in transit nodes and to the destination Connection Agent (CA). Among other information, the connection set-up message includes:

[0258] the parameters (m_i, σ_i², b_i) of the new connection i (the Connection Metric c_i=(R_i, m_i, b_i) can be derived from (m_i, σ_i², b_i)), and

[0259] the triplets (X_k, ε_k, ĉ_i,k) for each link k of the path.

[0260] TRANSIT CONNECTION MANAGER (TCM)

[0261] Upon receiving the connection set-up message, the Transit Connection Manager (TCM) of link k executes several verifications, including bandwidth management. The TCM:

[0262] 1. Extracts from the received triplets (X_k, ε_k, ĉ_i,k) the Equivalent Capacity ĉ_i,kof the connection. To do so, the Transit Connection Manager (TCM) correlates the (X_k, ε_k, ĉ_i,k) values of the triplets with its own (X_k, ε_k) values.

[0263] 2. Determines whether the connection is multiplexable or not, according to step 2 described above in the Path Selection section.

[0264] 3. Estimates the Link Metric L_kif the new connection is to be added using relations (5) and (6).

[0265] 4. Determines the link eligibility using relations (7) and (8).

[0266] 5. If the link is eligible, grants the bandwidth to the origin Connection Agent (CA), and updates the Link Metrics LA according to relations (5) and (6). The TCM eventually broadcasts the new values.

[0267] BANDWIDTH MANAGEMENT ACCORDING TO U.S. APPLICATION SER. NO. 97131

[0268] Non published U.S. patent application Ser. No. 97131 (IBM's reference FR 9 95 035) discloses a method and system for establishing new connections in the network while taking into account the dependance of these connections with other connections originated from the same port. The so called Dependent Connection Bandwidth Management process shown in FIG. 8 is based on:

[0269] 1. an accounting per port of all connections established on every link in the network.

[0270] 2. a modification of the path selection algorithm in the access node,

[0271] 3. an insertion of additional fields in the connection set-up message, and

[0272] 4. a modification of the Transit Connection Manager (TCM) algorithms in transit nodes.

[0273] PER PORT LINK ACCOUNTING

[0274] In the Route Controller of each node, a set of tables is defined, one for each port of the node. In particular for each port p a Dependent Connection Table DCT_pis maintained. This table comprises an entry for each link in the network and each entry includes the information required to manage the bandwidth of the link and the dependency of the port connections. The entry k of table DCT_pcorresponds to link k, and includes a quadruplet:

[0275] DCT_p(k)={l_k,M_k,B_k,E_k,^(N)}

[0276] DCT_pis called “Dependent Connection Table attached to port p”.

[0277] l_kis a bolean.

[0278] If l_k=1, then a “Dependent Connection Bandwidth Management” (DCBM) according to the present invention can be used on link k.

[0279] Else, the bandwidth management according to prior art (NBBS) is used.

[0280] M_krepresents the mean bit rate of the aggregation of the N_kconnections i issued from port p and using link k.

[0281] B_krepresents the mean burst duration of the aggregation of the N_kconnections i issued from port p and using link k.

[0282] E_k^(N)represents the Equivalent Capacity required on link k by the aggregation of the N_kconnections issued from port p and using link k:

[0283] E_k^(N)=f(R, M_k, B_k,X,ε)

[0284] where the function f is given by relation (1). $E_k^{\left(N_k\right)}=R\frac{Y_k-X+\sqrt{{\left[Y_k-X\right]}^2+4X{\rho }_k{Y}_k}}{2Y_k}$

[0285] where:

[0286] R is the port access rate,

[0287] Y_k=ln(1/ε)B_k(1−p_k)R, and

[0288] p_k=M_k/R.

[0289] PATH SELECTION

[0290] The Dependent Connection Bandwidth Management (DCBM) modifies the Path Selection process as explained hereunder. For each link k examined as a candidate for being part of the path, the computations and verification take into account the entries in the Dependent Connection Table DCT_p(k), and a bolean I_dcbminitialized to “1” at the beginning of the path search:

[0291] If I_dcbmAND I_k=1 then the Dependent Connection Bandwidth Management (DCBM) is used as detailed below.

[0292] Else, the bandwidth management according to prior art (NBBS) is used.

[0293] As the result of each iteration, a link k_select is selected, and the bolean I_dcbmis updated:

[0294] I_dcbm=I_dcbmAND I_k_select

[0295] The algorithm is executed for each link k if I_dcbmAND I_k=1. The Path Selection process comprises the steps of:

[0296] 1. Computing the Equivalent Capacity E′_k⁽ⁿ⁻¹⁾required on link k when the additional connection i with metric (R_i, m_i, b_i) is added to the aggregation of the N_kconnections issued from port p and already established on link k.

[0297] 2. Deriving the increase of the Equivalent Capacity ΔE_krequired to transport the additional connection.

[0298] 3. Computing the increase of the variance of the bit rate ΔV_k²of the aggregation of the (N_k+1) connections issued from port p and transported on link k.

[0299] 4. Determining whether the connection is multiplexable or not.

[0300] 5. Estimating the Link Metric if the new connection was to be added.

[0301] 6. Checking the link eligibility.

[0302] 7. Computing the load balancing weight of the link.

[0303] If the link k is eligible, the link ability to support the new connection is estimated by the load balancing weight of the link.

[0304] CONNECTION ESTABLISHMENT

[0305] Among other information, the connection set-up message includes:

[0306] the connection metric of the new connection i:

[0307] (m_i, σ_i², b_i)

[0308] a quintet for each link k of the path:

[0309] (X_k, ε_k, l_k, ΔE_k, ΔV_k²)

[0310] TRANSIT CONNECTION MANAGER (TCM)

[0311] Upon receiving the connection message, the Transit Connection Manager (TCM) associated to link k first tests the Boolean I_k.

[0312] If I_k=0, the Transit Connection Manager (TCM) executes the bandwidth management algorithms according to prior art (NBBS) as previously detailed.

[0313] If I_k=1, the Transit Connection Manager (TCM) executes the Dependent Connection Bandwidth Management (DCBM) algorithms. In particular, the TCM:

[0314] 1. Extracts from the receive quintets the increase in Equivalent Capacity ΔE_kand the increase in variance ΔV_k²due to the new connection.

[0315] 2. Determines whether the connection is multiplexable or not, according to step 2 described above in Path Selection section.

[0316] 3. Estimates the Link Metric if the new connection is to be added.

[0317] 4. Determines the link eligibility.

[0318] 5. If the link is eligible, grants the bandwidth to the origin Connection Agent (CA), and updates the Link Metrics.

[0319] IMPLEMENTATION

[0320] Path Selection.

[0321] The Path Selection must support the steps 1, to 7, described above in the Path Selection section and a Dependent Connection Table (DCT_p) must be defined for each port p attached to the node.

[0322] Connection Agent (CA)

[0323] The modification at the Connection Agent (CA) level includes in particular a change in the format of the connection set-up message with the definition of additional fields.

[0324] Transit Connection Manager (TCM)

[0325] The adaptation of the Transit Connection Manager (TCM) in transit nodes includes the handling of a new type of set-up message with additional fields and the support of steps 1, to 5, described above in the TCM section.

[0326] BANDWIDTH MANAGEMENT ACCORDING TO THE PRESENT INVENTION

[0327] The present application discloses an improved method and system for saving bandwidth taking advantage of the property of dependent connections while limiting the resources required for establishing connections in both access and transit nodes. More particularly, the object of the present application is to manage dependent connections in access nodes only without impacting transit nodes, and, to process the invention independently of the Path Selection algorithm and of the connection set-up.

[0328] In the following description, only a single class of service is considered. It should be clear that the extension to multi-priorities is straightforward. As illustrated in FIG. 9, the present invention is based on

[0329] 1. an accounting of the connections established on each of the links and issued from a same port,

[0330] 2. an accounting of the paths selected for connections issued from a same port,

[0331] 3. a path matching algorithm for comparing the path of connections issued from a same port,

[0332] 4. an algorithm for aggregating on each link the bandwidth of connections issued from a same port.

[0333] CONNECTION ACCOUNTING

[0334] In the Route Controller of each node, a set of tables is defined, one for each port of the node. In particular for each port p a Dependent Connection Table DCT_pis maintained. This table comprises an entry for each link in the network and each entry includes the information required to manage the bandwidth of the link and the dependency of the port connections. The entry k of table DCT_pcorresponds to link k, and includes a triplet:

[0335] DCT_p(k)={M_k,B_k,E_k,^(N)}  (10)

[0336] DCT_pis called “Dependent Connection Table attached to port p”.

[0337] M_krepresents the mean bit rate of the aggregation of the N_kconnections i issued from port p and using link k: $\begin{array}{cc}{M}_k=\sum _{i=1}^{N_k}{m}_i& \left(11\right)\end{array}$

[0338] B_krepresents the mean burst duration of the aggregation of the N_kconnections i issued from port p and using link k: $\begin{array}{cc}{B}_k=\frac{\sum _{i=1}^{N_k}{m}_i\times b_i}{\sum _{i=1}^{N_k}{m}_i}& \left(12\right)\end{array}$

[0339] E_k^(N)represents the Equivalent Capacity required on link k by the aggregation of the N_kconnections issued from port p and using link k:

[0340] E_k^(N)=f(R,M_k,B_k,X,ε)  (13)

[0341] where the function f is given by relation (1). $E_k^{\left(N_k\right)}=R\frac{Y_k-X+\sqrt{{\left[Y_k-X\right]}^2+4X{\rho }_k{Y}_k}}{2Y_k}$

[0342] where:

[0343] R is the port access rate,

[0344] Y_k=ln(1/ε)B_k(1−p_k)R, and

[0345] ρ_k=M_k/R.

[0346] PATH ACCOUNTING

[0347] In the Route Controller of each node, a set of tables is defined, one for each port of the node. In particular, for each port p, a Path Table PT_pis maintained. This table comprises an entry j for each connection j that originates from port p. Each entry includes the list of the links used by this connection. The entry j of Path Table PT_pcorresponds to connection j. Each entry j is of variable size, depending upon the path length (number of links along the path). In a preferred embodiment, the set of indexes used to address the links in the Path Table PT_pis the same as this used to address the entries in the Dependent Connection Table DCT_p.

[0348] FIG. 10 is an example of high speed packet switching network where 5 dependent connections (issued from a same port p) at node A have been established:

[0349] connection 1 from node A to node M: 4 links—6, 8, 14, 27.

[0350] connection 2 from node A to node H: 3 links—6, 9, 19.

[0351] connection 3 from node A to node N: 6 links—3, 1, 12, 16, 22, 33.

[0352] connection 4 from node A to node L: 4 links—6, 9, 18, 22.

[0353] new connection 5 from node A to node J: 4 links—6, 8, 14, 25.

[0354] The corresponding Path Table PT_pat access node A for port p is shown in FIG. 11. A connection index in the table identifies the dependent connections (connections 1 to 5) issued from port p. When a new connection i is established, the path of this connection is recorded as a new entry in the Path Table PT_p. For example, for new connection i=5 a 5th entry is added to the PT_p. The path length of this new connection 5 is equal to 4, that means that 4 links have been selected within the network to transmit traffic from origin node A to destination node J: links 6, 8, 14, and 25.

[0355] PATH MATCHING

[0356] FIG. 12 is a flow chart of the Path Matching algorithm. This algorithm identifies for each link k the dependent connections (connections issued from the same port p). At each new connection request, the algorithm compares in the Path Table PT_pthe path of the new connection i with the path previously selected for each existing connections j issued from the same port p. The algorithm identifies on the path selected for connection i all consecutive links, starting from the origin node, shared with dependent connections j. In the example shown in FIGS. 10 and 11, the Path Matching algorithm processed in view of the establiment of the new connection 5 along the routing path 6, 8, 14, 25 has identified a maximum of 3 (MAX_MATCH=3) consecutive links shared with at least another connection issued from the same port. These 3 consecutive links common with connections 1 and 5 are link 6, link 8 and link 14.

[0357] The Path Matching algorithm comprises the following steps:

[0358] (1200) The list of the links k selected for the new connection i is used in input of the Path Matching algorithm. K, the path length, represents the number of selected links. In the example illustrated in FIG. 11, i=5 and selected links=link 6, link 8, link 14, link 25, with m=1, 2, 3, 4, and K=4).

[0359] (1201) The Parameter MAX_MATCH is set to zero. MAX_MATCH will represent at the end of the algorithm the maximum number of links of a continuous path starting from the origin node (node A) and comprising links common with other connections j issued from the same port p.

[0360] (1202) The variable j (connection index) is set to one (selection of the first connection in the Path Table). This variable j identifies the connection j in the Path Table PT_p.

[0361] (1203) The following variables are initialized:

[0362] NLINK is set equal to the path length of connection j as it appears in the Path Table PT_p(as shown in FIG. 11, the path length of connection 1 is equal to 4).

[0363] NMATCH is set to zero. NMATCH represents the number from the origin node of links consecutively shared among connection i and connection j.

[0364] m=1: the first link of connection is selected. m is a variable used to select the mth link along the routing path of connections i or j. This mth link is counted from the origin node (node A).

[0365] (1204) A test determines whether the mth link of connection i is the same as the mth link of connection j or not:

[0366] If the selected link is shared among connection i and connection j, then

[0367] (1205) the value of NMATCH is updated:

[0368] NMATCH=NMATCH+1

[0369] (1206) m=m+1: the next link along the routing path of connections j and i is selected in the Path Table PT_p.

[0370] (1207) A test determines whether m is lower or equal than the path length NLINK of connection j (4 in FIG. 11) or not:

[0371] If m is lower or equal than NLINK, then:

[0372] (1208) A test determines whether m is lower or equal to K or not (K is the path length of connection i, K=4 in FIG. 11):

[0373] If m is lower or equal to K then the algorithm goes on with step (1204).

[0374] If m is not lower or equal to K then all links along the routing path of connection i have been processed and the algorithm goes on with step (1209).

[0375] If m is not lower or equal than NLINK, then the algorithm goes on with step (1209).

[0376] If the selected link is not shared among connection i and connection j, the algorithm goes on with step (1209).

[0377] (1209) A test determines whether NMATCH is higher than the maximum number MAX_MATCH:

[0378] If NMATCH is higher than MAX_MATCH then: (1210) MAX_MATCH=NMATCH

[0379] If NMATCH is not higher than MAX_MATCH then the algorithm goes on with step (1211).

[0380] (1211) The next connection in the Path Table PT_pis selected: j=j+1

[0381] (1212) A test determines whether j is lower than i or not:

[0382] If j is lower than i then the algorithm goes on with the next connection in the Path Table PT_pin step (1203).

[0383] If j is not lower than i then the algorithm is completed. All connections in the Path Table PT_phave been visited.

[0384] In the example shown in FIGS. 10 and 11, the variable MAX_MATCH is equal to 3. That means that the first 3 links counted from node A are shared among connection 1 and new connection 5.

[0385] CONNECTION AGGREGATION

[0386] The connection aggregation algorithm is executed on the links identified by the Patch Matching algorithm (links 6, 8, 14 as shown in FIG. 10). The connection aggregation algorithm comprises the steps of:

[0387] Computing the Equivalent Capacity E′_k^(N+1)required on link k when the additional connection i with metric (R_i, m_i, b_i) is added to the aggregation of the N_kconnections issued from port p and already established on link k:

[0388] E′_k^(N+1)=f(R,M′_k,B′_k,X,ε)  (14)

[0389] where: $M_k^{\prime }=M_k+m_i$ $B_k^{\prime }=\frac{m_i\times b_i+\sum _{j=1}^{N_k}{m}_j\times b_j}{m_i+\sum _{j=1}^{N_k}{m}_j}=\frac{m_i\times b_i+B_k{M}_k}{m_i+M_k}$

[0390] Deriving the increase of the Equivalent Capacity ΔE_krequired to transport the additional connection:

[0391] ΔE_k=E′_k^(N+1)−E_k^(N)  (15)

[0392] Note: ΔE_kis always less than the Equivalent Capacity ĉ, of the new connection i:

[0393] ΔE_k≦ĉ_i=f(R_i,m_i,b_i,X,ε)

[0394] Note: if link k does not transport other connections issued from port p (M_k=B_k0), then ΔE_kis equal to ĉ_i=f(R_k, m_i, b_i, X,ε).

[0395] FIG. 13 is a flow chart of the Connection Aggregation algorithm according to the present invention:

[0396] (1300) The Aggregation Algorithm is based on:

[0397] the connection metric of the new connection i (R_i, m_i, b_i)

[0398] the list of links k along the previously selected path.

[0399] the triplet (X_k, ε_k, ĉ_i,k) for each link k along the selected path.

[0400] the MAX_MATCH value resulting from the Path Matching algorithm.

[0401] (1301) Variable k is set to one. The first link of the selected path is selected.

[0402] (1302) The kth link of the selected path is selected.

[0403] (1303) M_k,B_kand E_k^(N)are read in the Dependent Connection Table DCT_pat the entry corresponding to link k:

[0404] M_k=DCT_p(k,1)

[0405] B_k=DCT_p(k,2)

[0406] E_k^(N)=DCT_p(k,3)

[0407] (1304) The mean bit rate M′_kand the mean burst duration B′_kof the connection i aggregated to the N_kconnections issued from port p and already established on link k are computed: $M_k^{\prime }=M_k+m_i$ $B_k^{\prime }==\frac{m_i\times b_i+B_k{M}_k}{m_i+M_k}$

[0408] (1305) The Equivalent Capacity required on link k when the additional connection i is added is computed:

[0409] E′_k^(N+1)=f(R,M′_k,B′_k,X,ε)

[0410] (1306) The increase of the Equivalent Capacity is computed:

[0411] ΔE_k=E′_k^(N+1)−E_k^(N

[0412] (1307) The Dependent Connection Table DCT_pis updated

[0413] DCT_p(k,1)=M′_k

[0414] DCT_p(k,2)=B′_k

[0415] DCT_p(k,3)=E′_k^(N+1)

[0416] (1308) The variable k is incremented to select the next link shared among dependent connections:

[0417] k=k+1

[0418] (1309) A test determines whether the variable k is lower or equal to MAX_MATCH or not:

[0419] If k is lower or equal to MAX_MATCH the aggregation algorithm goes on with step (1302).

[0420] If k is higher than MAX_MATCH the aggregation is completed. The connection message will include a triplet (X_k,ε_k,ΔE_k) for each link k consecutively shared among dependent connections.

[0421] The management of dependent connections takes advantage of the fact that it is not necessary to reserve more bandwidth than the port access rate for connections issuing from a same port. According to the present invention, the Path Selection algorithm is not involved in the management of dependent connections which simplifies the path selection algorithm and minimizes the time necessary for establishing connections. Furthermore, the claimed method and system does not imply the definition of a new type of connection set-up message and thus does not require any particular adaptation in transit nodes. Consequently, nodes supporting the present invention can inter-operate with existing nodes and the invention can smoothly and easily be introduced in existing networks (such as NBBS—Networking BroadBand Services).

[0422] When a new connection request is received, a path is first selected and then, dependent connections are managed. Compared with U.S. Pat. No. 97131, the path selection algorithm is no more optimal in that the path is selected a priori without taking any benefit of the dependency of the connections for choosing the best route. Furthermore, only a limited number of links (set of consecutive links along the selected path starting from the origin node) are selected by the path matching and connection aggregation mechanism. In reality, this drawback is not so important because most dependent connections are concentrated on links around the origin node. The closer to the origin node links are, the higher the probability to find dependent connections is.

[0423] The present Dependent Connection Management is not limited to a specific protocol such as Frame Relay (FR) but can be used to improve any service offering that uses a shared access medium, like ATM.