Abstract:
A system and method are described for a semi-permanent virtual circuit (SPVC) manager to manage a network of switches coupled together to form a semi-permanent virtual circuit. The SPVC manager considers connection resources internal to the network throughout the network when managing the SPVC. The SPVC manager uses either a static flow control window or a dynamically sized flow control window to manage pending connections within the network.

Description:
FIELD OF THE INVENTION 
     The field of the invention relates to networks for digital communication. More specifically, the field relates to the reduction of network-wide control message congestion. 
     BACKGROUND 
     A soft or semi-permanent virtual circuit (“SPVC”) is a generic term for any communications medium that is permanently provisioned at the end points, but switched in the middle. An example of an SPVC is illustrated in  FIG. 1 . An SPVC through an asynchronous transfer mode (“ATM”) network comprises permanent virtual circuits (“PVC”)  100  at the entry  110  and exit  120 . A switched virtual circuit (“SVC”)  130  connects the entry  110  and exit  120 . Individual switches  140  or nodes allow for different switched virtual paths (“SVP”) to connect the entry  110  and the exit  120 . At the entry (originator)  110  device and the exit (target)  120  device, the PVC is cross-connected to the SVC. 
     In a private network-network interface (“PNNI”) network provisioned with primarily SPVC connections, the demand on control resources remains low until significant changes are precipitated by a failure in the network. A link or node failure may necessitate the rerouting of thousands of SPVCs. This activity results in a burst of call release, setup, route selection, and call connect activity as connections are released (de-routed) and rerouted over alternate paths, all in a relatively short period of time. 
     When a trunk fails at the PNNI, call clearing is initiated on both sides of the failed trunk by sequentially sending release messages for every failed connection. Once the SPVC manager  150  at the master endpoint  120  receives a release, the SPVC manager initiates a reroute of the connection by sending a setup message into the network. In an effort to conserve switch resources, the SPVC manager reacts to local node congestion, avoiding the sending of setup messages to an already congested switch. 
     Simulations of up to 100 node networks with failures of links carrying tens of thousands of connections provide evidence that large numbers of setup messages can be dropped at the switches at or near each end of the failed link. These drops, and the ensuing retries, significantly increase the time required for the network to recover from a failure. In these scenarios, reacting to local node congestion yields only a moderate effect on helping the SPVC manager send reroute messages into the network without causing congestion at a distant node. Although local switch congestion may be abated at the connection end nodes, evidence suggests that congestion will not be avoided in the core of the network. 
     SUMMARY OF THE INVENTION 
     Embodiments are described for a semi-permanent virtual circuit (SPVC) manager to manage a network of switches coupled together to form a semi-permanent virtual circuit. The SPVC manager considers a set of pending connections throughout the network when managing the SPVC. The SPVC manager uses either a static flow control window or a dynamically sized flow control window to manage pending connections within the network. 
     Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references indicate similar elements and in which: 
         FIG. 1  is a block diagram illustrating a prior art semi-permanent virtual circuit. 
         FIG. 2  is a block diagram of a semi-permanent virtual circuit manager interface. 
         FIG. 3  is a flowchart of a method of responding to congestion. 
         FIG. 4  is a flowchart of a method of dynamically sizing a flow control window. 
     
    
    
     DETAILED DESCRIPTION 
     A system and method are disclosed for reducing congestion within a soft or semi-permanent virtual circuit (“SPVC”) by factoring in pending connections network-wide rather than simply at the local switch. Flow control windows regulate the number of connections pending in the network. The flow control windows comprise either a static window scheme based on configurable static parameters or a dynamic window-sizing scheme based on network-wide signaling congestion indications. 
     To avoid congestion in the core of the network, a network-wide perspective is used. The SPVC manager is designed to consider the number of connections pending in the network rather than just the number pending at the local switch. 
     Each switch in the network has one SPVC manager that manages all of the connections that the switch oversees as a master. The SPVC manager ( 200 ) interfaces with a call control block (CCB) ( 205 ) as illustrated by the block diagram of  FIG. 2 . The SPVC manager ( 200 ) initiates setup messages and is responsible for SPVC retry operations. A virtual switch interface (VSI) master ( 210 ) software module controls virtual switch interface (VSI) slaves present on the CCB ( 205 ). For one embodiment, the VSI slaves include the SPVC manager ( 200 ), an interface manager or virtual circuit manager (IFM/VCM) ( 215 ), and a connection manager or resource manager (CM/RM) ( 220 ). The IFM/VCM ( 215 ) allocates interfaces to the SPVC manager ( 200 ) and the CM/RM ( 220 ) allocates connections to the SPVC manager ( 200 ). The SPVC manager ( 200 ), when forming a connection with a specified address, requests a route from the routing agent ( 225 ) and forwards the route to the call processor ( 230 ). For one embodiment, the routing agent ( 225 ) requests a route from a private network-to-network interface (PNNI) ( 235 ). For one embodiment, the call processor ( 230 ) includes a call control ( 240 ) for processing the route provided by the route agent ( 225 ) and a signaling module ( 245 ) to interact with the service specific connection oriented protocol (SSCOP) ( 250 ). A redundancy manager ( 255 ) makes the SPVC managed by the SPVC manager ( 200 ) persistent and redundant. A call scaling module ( 260 ) scales the calls as requested by the SPVC manager ( 200 ) 
     Routing software monitors many points where resources may be under pressure at the switch. Congestion indicators are set when a high threshold is reached and are cleared when a low threshold is reached. These congestion indicators include (1) local node setup congestion for connections pending at the node, (2) connection resource manager mild congestion for connect and delete requests queued to the connection resource manger, and (3) connection resource manger severe congestion. The high and low congestion thresholds for these parameters are all configurable. The call control and the SPVC manager software use these congestion indicators to determine if local congestion abatement actions should be taken. The SPVC manager stops sending setup messages whenever there is any indication of local congestion. 
     A variety of schemes are available to determine when network-wide abatement actions are to be taken, in contrast to local congestion abatement. One method for determining network-wide abatement is a static flow control window. In this scheme, the SPVC manager  200  keeps track of the number of its connections owned by this SPVC manager that are pending anywhere in the network. The algorithm simply limits the maximum number of pending connections to the configured static window size. The optimal size of the static flow control window is based on a number of factors. These factors include the number of nodes in the network, the geographical size of the network, and the distribution across SPVC originating nodes for routing of connections across one link. The latter factor is explained as follows. If most or all of the connections are concentrated in one switch or node that has a small window, and if that switch were to go down, then rerouting would be extremely slow. Assigning a large window to the switch would help to improve flow control. Therefore, if connections are concentrated in a few nodes, then larger windows are optimal for those nodes. If connections are not concentrated in a few nodes, then smaller windows are optimal for the nodes. 
     A more efficient scheme uses a dynamically sized window based on network-wide congestion indications. Each switch in the network has an impending congestion monitor. The monitor maintains counters of pending connection add and delete requests. For one embodiment, the monitor&#39;s thresholds are set to one-half the resource connection manager mild congestion thresholds to act as an early warning that congestion is building. At every switch, the impending network-wide congestion status or indication is recorded in every outgoing connect message. 
       FIG. 3  is a flowchart of the actions of the call control block  240  of  FIG. 2 , including the setting of a network-wide congestion indicator in a connect message. As described below with respect to  FIG. 4 , the SPVC manager  200  in turn monitors the network-wide congestion indicators in connection messages as part of the process of controlling the size of the congestion window. As shown in  FIG. 3 , if there is no congestion (Block  305 ) and the release queue is empty (Block  310 ), the SSCOP sends setup, connect, and release messages (Block  315 ). If the release queue is not empty (Block  310 ), release messages are processed (Block  320 ). If severe congestion is indicated (Block  325 ), setup and connect messages continue to be dropped (Block  330 ) and release messages are queued (Block  335 ). When severe congestion abates (Block  340 ), setup and connect messages continue to be dropped (Block  345 ). The call control processes release messages from the queue until the queue is empty and then processes any messages from SSCOP (Block  350 ). If mild congestion is indicated (Block  355 ), SSCOP drops setup and connect messages (Block  360 ). When mild congestion abates (Block  365 ), the call control block  240  processes connect and release messages from SSCOP on a first-come, first-serve basis. At block  370 , a determination is made whether a message is a release message or a connect message. If the message is a release message, the release message is processed at block  372 . If the message is a connect message, then at block  374  the network-wide congestion indicator or flag in the connect message is set and the connect message is processed. 
     If there is local node setup congestion (Block  375 ), SSCOP drops setup messages (Block  380 ). When all congestion abates (Block  385 ), the call control  240  processes setup, connect, and release messages on a first-come, first-serve basis (Block  390 ). A ten second timeout is implemented for each setup or connect message that is dropped at SSCOP. 
     The SPVC manager  200  monitors network-wide congestion information in connect messages that the SPVC manager  200  receives. Thus a connect message with a network-wide congestion indicator set as shown in Block  374  of  FIG. 3  would be monitored by SPVC manager  200 . The SPVC manager  200  thus extracts the network-wide congestion information from the connect message network-wide congestion indicator. 
     The SPVC manager  200  of  FIG. 2  controls the size of the congestion window, as shown in the flowchart of  FIG. 4 . At the SPVC manager  200  the dynamic window size is configured to have a lower limit (MINCONN) and an upper limit (MAXCONN) (Block  400 ). For one embodiment, the lower limit is set to five pending connections and the upper limit is set to 500 pending connections. For a further embodiment, the initial window size (DYNWIN) is set to the lower limit (Block  410 ). The individual nodes of the network are monitored for congestion (Block  420 ). If the network-wide congestion indicator is set in a received connect message (Block  430 ), the window size is decreased by a percentage of the window size (Block  440 ). For one embodiment, the window size is decreased by 12.5%. If the connection is completed with no congestion indication (Block  430 ) and if connection activity has occurred within a specified period at the SPVC manager (Block  450 ), the window size is increased by a percentage of the lower threshold until the maximum window size is reached (Block  460 ). For one embodiment, the window size is increased by 10% of the lower threshold. If no connection activity has occurred for the specified period at the SPVC manager (Block  450 ), the window size is reset to the minimum threshold (Block  410 ). For one embodiment, the specified period is 10 seconds. 
     The method described above can be stored in the memory of a computer system as a set of instructions to be executed. The instructions to perform the method described above could alternatively be stored on other forms of machine-readable media, including magnetic and optical disks. For example, the method of embodiments of the present invention could be stored on machine-readable media, such as magnetic disks or optical disks, which are accessible via a disk drive (or computer-readable medium drive). Further, the instructions can be downloaded into a computing device over a data network in a form of compiled and linked version. 
     Alternatively, the logic to perform the methods as discussed above could be implemented by computer and/or machine readable media, such as discrete hardware components, large-scale integrated circuits (LSI&#39;s), application-specific integrated circuits (ASIC&#39;s), firmware such as electrically erasable programmable read-only memory (EEPROM&#39;s); and be implemented by electrical, optical, acoustical, and other forms of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.), etc. 
     Although the present invention has been described with reference to specific exemplary embodiments, it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the invention. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.