US 6130877 Rate controlled broadcast for activation of entities in large scale data networks

ABSTRACT – A broadcast methodology for activation of virtual circuits in a large scale data network at a controlled rate is disclosed. The method includes, at a node within the network, alternate steps of broadcasting activation signals for a predetermined number of the of virtual circuits and delaying a time interval. The alternate steps are repeated until all the activation signals have been broadcast.

FIELD OF THE INVENTION

The present invention generally relates to data communications networks and, in particular, to a broadcast methodology for activation of network entities in a large scale data network at a controlled rate.

BACKGROUND OF THE INVENTION

With respect to data communications, as represented in FIG. 1, a data network 10 may be generally characterized by a plurality of nodes 12 interconnected, for example, by trunks 14 and/or by virtual circuits 16 through which two nodes are communicatively coupled, whereby data is transferred between the nodes 12 of the network 10. The nodes 12 embody processors which effect various functions within the network 10. Certain nodes 12 may be provisioned with links 18 each of which functions as a data communications service access line, typically used by customer premise equipment (not shown) to access the data network 10. Frame Relay Services carrying data between network nodes 12 manifested by Nortel’s Magellan Passport product is an example of conventional data communications.

Data networks 10 have evolved rapidly in the last few years, for instance, increasing by a 2 or 3 order of magnitude in both the speed of data transfer (e.g., from 9600 bits/second to 50 megabits/second) and the number of virtual circuits 16 that are present in such networks (e.g., from 500 to 500,000 or higher). As a consequence, technical problems need to be solved in order to create reliable data networks 10 that are so much faster and higher in complexity, from the technology base of earlier, smaller networks.

A significant problem is the amount of processing demands on the network nodes 12 to supervise and control the state of a large number of network entities, such as, the trunks 14, virtual circuits (VCs) 16 and corresponding data link connection identifiers (DLCIs) paired with each VC, links 18 (i.e. access lines), and the like.

Network speeds are much faster. As the volume of control messages is relatively low in comparison to activity each can produce, with respect to high speed networks, demands on a single node 12 for control of large amounts of network entities seem to arrive instantaneously at the network node 12 which may not have sufficient processing resources or capacity to process the large number of demands, thereby overloading that node.

The various nodes 12 in the data network 10 have no easy means to communicate with each other in relation to the large numbers of network entities which require supervision. Also, modern software practices typically implement each network entity in software as an object, that act independently of other objects, even in the same processor. Furthermore, all demands on load typically are generated as quickly as possible because, according to conventional wisdom, it is preferred to have the network 10 react as quickly as possible to network affecting events.

Network events can occur that trigger supervisory activities on large numbers of the network entities. These activities typically are initiated in response to some event occurring within the data communications network 10 in respect of a particular node and that node in turn may broadcast respective control messages for the network entities affected by the event, to one or more other nodes. Examples of possible network events include:

activation or outage of a data communications service containing a large number of DLCIs and corresponding VCs 16, for example, a link 18 which previously was not functioning now becoming operational or the link 18 which previously was functioning now becoming non-operational;

disconnection of the trunks 14 connecting a network node 10 to other node and its subsequent restoration; and

reset of a network node 12 that handles a large number of network entities and its subsequent restoration.

Such events can easily produce very large demands, in terms of processing resources, on different nodes 12 in the network 10. If not handled properly, overloading of these nodes can either cause failure in the restoration of the required activity, for example, by the activity taking so long that it exceeds the time-out values for replies or in extreme cases, failure of other nodes 12 by exhaustion of memory or queue resources on those nodes.

Since such drastic actions are usually triggered by initial errors, this instantaneous large resource demand, referred to herein as tidal waves, makes required stability of data networks–the ability to keep operating and the ability to recover from failures–difficult to achieve. For example, initial failure of a particular network node 12 can produce tidal waves though the network 10, which waves then cause other network nodes 12 to fail, thereby resulting in complete paralysis of the entire network 10.

Therefore, measures need to be taken to safeguard large data networks from such drastic failures.

A direct approach to prevent tidal waves is for network nodes 12 that are low in resources to inform other nodes. Such congestion messages should cause the potential originator node 12 in the generation of a tidal wave to slow down and prevent tidal waves that are damaging. However, technology to monitor and inform on resource utilization, especially on a fast and transient basis, does not exist in standard form across the data network 10. The overloading can occur so fast that messages to ask the originator node 12 to slow down can easily be too late. Also, since there are so many network entities, such resource backing messages can easily themselves cause tidal waves if each network entity is responsible for checking resources.

If some supervisory entities (a smaller number of entities) in a network node are responsible, then it is very costly for that supervisor to find exactly which of the numerous entities are responsible for resource exhaustion and to ask them to desist. The complexity of any such system is very high, and it is very costly to produce and to verify their correct operation.

Another approach to prevent tidal waves is for any generating network node to query the receiver network node and make sure that it receives a proceed signal before starting the activity that involves the numerous network entities. This approach generates traffic and resource demand in itself, during times when the data network may be severely stressed, and may thus itself be a destablizing factor. Since there are numerous network entities that are independent of each other, the cost of such an authorization system will be as costly to network resources as the original activity. A query has to be sent to authorize each transaction. Such a system will slow down significantly the speed within which the needs of the numerous network entities are serviced. Large amounts of complexity is introduced to handle cases where proceed signals are not acknowledged. The sender will have to go through its lists of network entities and try again several times.

Hence, a methodology that prevents generation of tidal waves within a data communications network is desired.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide a new and improved broadcast methodology for use in data communications networks.

The invention, therefore, according to a first broad aspect provides in a data communications network, a method of broadcasting signals from one node to a plurality of nodes comprising alternate steps of, at the one node: broadcasting the signals to a portion of the plurality of nodes; and delaying a predetermined time interval; whereby the alternate steps are repeated until the signals have been broadcast to all of the plurality of nodes.

In accordance with a second broad aspect of the invention, there is provided in a data communications network, a method of broadcasting signals comprising the steps of: recognizing occurrence of an event at a node; determining network entities which are affected by the recognized event; and broadcasting, by the node, related event signals corresponding to the recognized event to the affected network entities substantially at a controlled rate.

In accordance with a third broad aspect of the invention, there is provided a method for slowing down activation of a plurality of virtual circuits by a node in a data communications network, comprising alternate steps of: broadcasting activation signals for a predetermined number of the plurality of virtual circuits; and delaying a time interval; whereby the alternate steps are repeated until all the activation signals have been broadcast.

In accordance with a fourth broad aspect of the invention, there is provided in a data communications network, a method for activating of a plurality of virtual circuits by a network node providing communications service access to the network, comprising alternate steps of: broadcasting, by a communications service access process executed at the network node, activation signals to a number of connection identifier processes associated with the virtual circuits, the connection identifier processes providing the activation signals to corresponding virtual circuit processes which send activation messages through the network; and delaying a time interval; whereby the alternate steps are repeated until activation signals for all of the plurality of virtual circuits have been broadcast.

In accordance with a fifth broad aspect of the invention, there is provided in a data communications network, a system of broadcasting signals from one node to a plurality of nodes comprising: means for broadcasting the signals to a portion of the plurality of nodes; and means for delaying a predetermined time interval; whereby the means for broadcasting and the means for delaying operate alternately and repeatedly until the signals have been broadcast to all of the plurality of nodes.

In accordance with a sixth broad aspect of the invention, there is provided in a data communications network, a system for broadcasting signals comprising: means for recognizing occurrence of an event at a node; means for determining network entities which are affected by the recognized event; and means for broadcasting, by the node, related event signals corresponding to the recognized event to the affected network entities substantially at a controlled rate.

In accordance with a seventh broad aspect of the invention, there is provided a system for slowing down activation of a plurality of virtual circuits by a node in a data communications network, comprising: means for broadcasting activation signals for a predetermined number of the plurality of virtual circuits; and means for delaying a time interval; whereby the means for broadcasting and the means for delaying operate alternately and repeatedly until all the activation signals have been broadcast.

In accordance with a eight broad aspect of the invention, there is provided in a data communications network, a system for activating of a plurality of virtual circuits by a network node providing communications service access to the network, comprising: means for broadcasting, by a communications service access process executed at the network node, activation signals to a number of connection identifier processes associated with the virtual circuits, the connection identifier processes providing the activation signals to corresponding virtual circuit processes which send activation messages through the network; and means for delaying a time interval; whereby the means for broadcasting and the means for delaying operate alternately and repeatedly until activation signals for all of the plurality of virtual circuits have been broadcast.

To prevent the building of large tidal waves, each network node, when generating loads for other network processors, preferably slows themselves down to a not exceed a maximum rate, independently of the state of other processors.

This independent process removes most of the complexities and pitfalls of active systems in the large network to try to prevent tidal waves. No further data is generated to remove faults that can themselves become tidal waves. Each network node does not need instantaneous knowledge of the state of other network nodes.

When network events occur that would otherwise result in the generation of tidal waves, this slowing down of the generation of the load transforms the potential tidal waves into a smooth flow, the rate of which is controlled.

This approach attempts to ensure that failures or other events in a single network node alone will not generate sufficient activities that will congest remote network nodes, because the tidal wave is tamed to a smooth flow.

The predetermined rate of generation of broadcast loads on remote processors, preferably, can be set so that by itself, a node will not overload any remote processor even in the worst case. By doing this, destructive tidal waves may be prevented from originating by any single node affected by some event, such as, node failure. Typically, not all of the numerous network entities correspond to a single remote processor and thus this rate should provide a comfortable margin of safety. However, for extra margins of safety, at the cost of a longer restoration time for network failures or a longer time for networks to change its configuration, the predetermined rate may be slowed down further so that double or triple network node failures will not cause flows large enough to cause further harm to the network.

Since no active interaction occurs between network nodes during broadcast, this method can be verified and the speed determined by looking only at one generating node set at maximum size such that it is set up to direct all its load to a single remote node. That is the worst case condition for the test, and any network interaction will be less strenuous than that amount.

 

Related Posts