Centralized Load Minimizing Method for Periodical Routing Verification Tests Scheduling

The present invention relates to a method for auditing routing table information in a packet switching network. In particular, it relates to a method of scheduling tests to check the correctness of routing table information associated with respective switching nodes or signal transfer points of Signaling System No. 7 (SS7) networks.

Routing of messages from a source node to a destination node in networks, such as for example packet switched networks (PSN's), is performed automatically by the use of routing tables. A routing table is located at each node of the network and contains information as to the link set between nodes that the message is to be transmitted. This information usually includes a preferred or normal route and one or more secondary or failure routes.

Signaling System No. 7 (SS7) interconnects stored program control exchanges, network data bases and intelligent peripherals of telecommunications management networks. SS7 is used to exchange messages and information respectively related to call management and to distributed applications and network management. The protocols of SS7 have been standardized by the "Comite Consultatif International pour le Telephone et le Telegraphe" (CCITT) which is known today as the International Telecommunications Union (ITU)--Telecommunications Standardization Sector (TSS).

To operate properly, the correct routing table information is loaded and to stored in each table at system start-up or generation. This information is constant and the routing table is described as "static". The routing tables may also be described as "partial path" because the information stored in each table relates only to the next node on the way to the destination. The integrity of the routing information stored in the tables is fundamental to the normal functioning of the network.

Network communication problems arise when the routing information in tables is incorrect or becomes corrupted. One example of a problem is when the table fails to contain an entry for a destination node causing the message to stop at that node and to fail to make it to its destination. Another problem example occurs when two or more node tables contain destination information directed to each other resulting in the message traveling in an endless loop. A third message transmission problem occurs when the message tree between the source node and the destination node results in an excessive length route where the message crosses more STP's than the maximum allowed STP's in the network. Still yet another problem occurs when the signal path through the network is unidirectional. That is to say the message can travel in one direction through the tree from the source node to the destination node but it cannot travel in the reverse direction from the destination node to the source node.

In SS7 networks there are currently two methods used to check the correctness of SS7 routing tables.

The first method involves checking "off-line" the correctness of the routing data before the introduction of this data to the tables. Various simulation methods are used for to check the information. The problem with this method resides in errors introduced during the manual data entry of the information in the table for each node by the operational staff. Further, data corruption can occur after entry. This "off-line" method of testing table data information does not safe-guard against errors occurring during loading of the data in the tables or against errors due to data corruption.

The second method used to check the correctness of SS7 routing tables is a real time check of the table routing data in the network. It consists of auditing "on-line" during network operation the routing data after it has been introduced in the tables. There are two known "on-line" tests in use today to check the correctness of SS7 routing data. These tests are known as the Message Transfer Part (MTP) Routing Verification Test (MRVT) and the Signaling Connection Control Part (SCCP) Routing Verification Test (SRVT). The MRVT and the SRVT check respectively the content of the Message Transfer Part (MTP) routing tables and the content of the SCCP routing tables. These tests are initiated at one or more predetermined source nodes to test the routes messages will follow to respective predetermined destination nodes. Usually each test results in the message following all possible routes to its test destination. This is done by sending multiple test messages and tracking the identities of all nodes crossed by the message. Information on the success of this testing is transmitted back to the destination node. An example of an "on-line" testing procedure is disclosed in U.S. Pat. No. 4,745,593 issued May 17, 1988 to Gilbert M. Stewart.

One problem associated with this routing verification testing is the extra network loading associated with the testing. The networks are already operating under time restraints to deliver messages between source nodes and destination nodes. The introduction of the "on line" testing to be thorough should be conducted periodically in the SS7 network as suggested by the ITU-TSS standards. During each period, from evenly node, a test is run against all the destinations which can be reached from the node. For example, if a network has 20 nodes, there could be hundreds of possible test routes to follow in one test. This one test could significantly load the network. SS7 networks are signalling networks with very stringent delay objectives that the networks can hardly meet when they are overloaded. Consequently, operators are reluctant to perform tests of routing tables in networks. In view of the foregoing, it can be appreciated that there is a problem with routing table information and the verification of that information particularly after the table information has been loaded into the network. There does not appear to be a solution available to the operator to check periodically "live" information without the risk of unduly overloading the network with test messages and placing legitimate messages at risk of being lost. This risk is more serious when many tests are started at the same time or very close in time such that several tests are running at the same time.

In accordance with an aspect of the present invention there is provided a method for scheduling verification tests to audit routing information in a packet switching network. The method preferably involves utilizing the operation system of a telecommunications management network (TMN) to control the testing of the network.

The method of the present invention involves scheduling verification tests to audit routing information in a packet switching network comprising a plurality of packet switching nodes and a plurality of bi-directional links each interconnecting a distinct pair of said nodes. The packet switching network has associated therewith a telecommunications management network, comprising an operation system connected to each of said nodes through respective interfacing links. The method is controlled by the operation system and includes the steps of:

1) selecting a test time duration period for scheduling the verification tests of is the routing information in the network,

2) selecting a number of nodes to be tested and determining sub-tests to be made to all destination nodes from each node in the network to be tested,

3) generating a time test interval based on the quotient of the scheduled test time duration period by a total number of sub-tests to be conducted from each node to be tested, and

4) scheduling the verification tests during the time duration period by staggering starting of each verification test by an interval which is a function of the time test interval so as to disperse the traffic loading induced on the network by the verification tests.

The method for scheduling routing verification tests of the present invention has the advantage in that it disperses the load induced on the network by running these verification test periodically over a test time frame and thereby minimizes the risk of overloading the network.

It should be understood that the TMN is a management network which is conceptually separated from the telecommunications network. The TMN is specified in CCITT recommendation M.3010 and herein incorporated by reference.

The method may select the test time duration period for scheduling the verification tests from off peak demand hours. Preferably, the off peak demand hours are selected between 1:00 a.m. and 4:00 a.m. Also, the verification test preferably is selected from one of a message transfer part routing verification test and a signalling connection control part routing verification test in an SS7 signalling system.

It should be understood that the operation system represents the supervisory or control systems of the TMN. It should also be noted that the operation system is defined in CCITT recommendation. M.3010 previously mentioned. In accordance with another aspect of the present invention there is provided a system for scheduling verification tests to audit routing information in a package switching network comprising a plurality of package switching nodes and a plurality of bi-directional links each interconnecting a distinct pair of the said nodes. The packet switching network has associated therewith a telecommunications management network. The system includes an operation system functioning independently and remotely of the packet switching network and forming part of the telecommunications management network. Interfacing links are connected between the operation system and respective ones of the switching nodes for communicating control signals between the operation system and each node of the network. The operation system includes means for selecting a test time duration period for scheduling the verification tests of the routing information network, and means for selecting the number of nodes to be tested and determining sub-tests to be made to all destination nodes from each node in the network to be tested. The operation system includes means for generating a time test interval based on the quotient of the scheduled test time duration period by a total number of sub-tests to be conducted. The operation system then schedules the verification tests over the time duration period by staggering starting of each verification test by an interval which is a function of the time test interval so as to disperse the traffic loading induced on the network by the tests.

For a better understanding of the nature and objects of the present invention reference may be had to the accompanying diagrammatic drawings in which:

FIG. 1 illustrates the interrelationship between the telecommunications management network and the switching network of the present invention.

FIG. 2 illustrates a correct routing table for the switching network of FIG. 1;

FIG. 3 illustrates message tree for the switching network of FIG. 1 and routing table of FIG. 2; and

FIG. 4 is a flow chart of the steps performed by the operation system of the present invention.

Reference will be made to FIGS. 1 to 3 to describe a typical network and routing of messages within that network.

Referring to FIG. 1 there is shown a switching network within the broken lines 10. Switching network 10 includes 6 switching nodes or signalling transfer points labeled 12, 14, 16, 18, 20, and 22. The illustrated network has been drawn to illustrate a start or initiation node 12, a destination node 22 and intermediate nodes 14, 16, 18, and 20. It should be understood that for the purpose of this description, the start node 12 and the destination node 22 may be intermediate nodes in other signal transfers, but have been so designated for the purpose of defining one verification test to be conducted by the method of the present invention.

The switching network of the preferred embodiment of the present invention shown within broken line 24 is a CCITT SS7 network. Each of the nodes 12 through 22 respectively shown within the network includes a routing table associated therewith for routing a signal along one or more link sets to a subsequent node in the routing of the signal within the network. The routing table information is both static and partial path. The link sets between the nodes are shown by link set connection 26 between nodes 12 and 14, link set 27 between nodes 12 and 20, link set 28 between nodes 12 and 16, link set 30 between nodes 16 and 20, link set 32 between nodes 14 and 20, link set 34 between nodes 14 and 18, link set 36 between nodes 18 and 20, link set 38 between nodes 20 and 22, link set 40 between nodes 16 and 22, and link set 42 between nodes 18 and 22.

Referring to FIG. 2 there is shown an example of the routing table information for each of the nodes 12 through 20. In the middle column of Table 1, the primary link set is defined as the preferred or primary route along which a message or a signals transferred from the node defined in the left most column. The right most column indicates alternative link sets along which a signal will pass or travel in the event the primary path is either disabled or busy. Accordingly, a message at node 12 will be sent primarily along link set 27 to node 20. In the event a message cannot be sent along link set 27, node 12 will switch the message to send it either along link set 26 to node 14 or link set 28 to node 16. Likewise, node 14 will primarily send its message over link 32 to node 20 however, in the event that node link 32 is busy or not able to function, node 14 will route its message along link 34 to node 18. Node 16 has primary route along link set 40 to rode 22. In the event that the signal cannot travel along link set 40, node 60 will direct its message along link set 30 to node 20. Node 18 has a primary message routing along link set 42 to node 22 and a secondary or alternate path along link set 36 to node 20. Node 20 has a primary route along link set 38 to node 27. In this example, node 20 has no alternative link set route.

With this routing information table in FIG. 2, a message initiated at node 12 having a destination of node 22 may follow a route to the destination node through several different switching nodes depending on the channels that are open for communicating the messages between the nodes.

Referring to FIG. 3 there is shown a message tree for the SS7 network portion of FIG. 1 and the routing table of FIG. 2. From the message tree of FIG. 3, it can be seen that there are potentially 6 working paths through different nodes that the message can follow to get to the destination node 22 from the initiation or the starting node 12. The primary route for a message to travel from staff node 12 to destination node 22 is (from FIG. 2) along link set 27 to node 20. Once the message is at switching node 20, switching node 20 would direct the message along link set 38 to destination node 22. In the event these channels or link sets are not open, then an alternative route would be determined to the destination node 22 from the staff node 12 through which a communication channel would be set up for transferring the message.

It should be understood from FIG. 3 that to run one verification test on this network to check the integrity of the routing tables of the nodes from the source node 12 to the destination node 22 will result in the generation of many test messages. For each branch in the tree, a transmit message and an acknowledgment message will be generated. There are 13 branches between the nodes of the test FIG. 3 which results in a total of 26 transmit and acknowledge messages being generated. A further 6 receive messages are generated at destination node 22 since there are 6 paths to reach this node. To expand the verification testing to all nodes in a network that can have anywhere from 20 to upwards and beyond 100 nodes, will result in a very high load demand being placed on the network.

Referring again to FIG. 1 there is shown at 50 an operation system. The operation system forms part of the telecommunication management network shown diagrammatically within broken lines 51. The operation system is connected through a general purpose interface which has been referred to as a "Q3" interface. These Q3 interfaces have been defined in CCITT recommendation M.3100. Each interface is connected to a respective node in the SS7 switching network. The interface from the operation system 50 to node 12 is labeled 52, to node 14 is labeled 54, to node 16 is labeled 56, to node 20 is labeled 58, to node 18 is labeled 60, and to node 22 is labeled 62.

It should be understood that the operation system is part of the telecommunications management network hierarchy that runs various controls on the network to insure that the network is operating properly and to control the operation of the actual signalling system of the network. It is through this operation system that the present invention schedules the verification tests to be run on the nodes of the network.

Referring now to FIG. 4 there are shown the steps involved in the method used by the operation system 50 of the present invention in scheduling the periodic staggered start times for commencing verification tests in the network. The first two steps in the method are shown in FIG. 4 at 100 and 110. The first step 100 is for the operation system to select the test time duration period. The second step in the method is for the operation system to select a number of nodes to be tested and determine sub-tests to be made from each selected node to all other nodes in the network. It should be understood that these steps 100 and 110 may be reversed in order or may be carried out simultaneously by the operation system 50. The operation system 50 selects the test time duration period from low demand or off peak demand hours. This would be early in the morning between 1 a.m. and 4 a.m., local time. It should be understood however, that the length of this time interval may be varied on a daily basis depending on the demand on the network. Step 110 involves the selection of a number of nodes to be tested by the operation system 50. Also at this step, the number of sub-tests to all destination nodes in the network from the selected test node is determined by the operation system 50. While preferably all nodes in the network should be tested during the selected test time duration period, if the period is not sufficiently long enough to run all the test without tests overlapping, then the number of nodes to be tested may be reduced.

The operation system at step 120 generates a test start time interval which is a function of the test time duration period and the total number of sub-tests to be made from each node selected to be tested. The test time interval is preferably based on the quotient of the scheduled test time duration period and the total number of nodes to be tested.

At step 130 the operation system 50 commences a first verification test at the beginning of the time test duration period.

At step 140 each successive verification test to be conducted in the system is selected by the operation system 50. The operation system 50 continues to test each successive node after the duration of a time interval has lapsed.

From the foregoing it can be seen that the operation system will include means for scheduling the verification tests of each node by staggering the starting time of the verification tests over a pre-determined time period at pre-determined time intervals.

In the network illustrated in FIG. 1, the test time duration period is preferably selected from the hours between 1 a.m. to 4 a.m. This gives a duration of three hours or, ninety minutes. The network of FIG. 1 comprises six nodes. Form each one of the nodes a sub-test can be run from all the other nodes. This gives the number of five sub-tests from each node. The total number of tests is therefore 5.times.6 meaning thirty sub-test. The time test interval is the quotient of the scheduled time duration, ninety minutes, and the total number of sub-tests to be conducted, thirty. This gives the time test interval of three minutes. The operation system 50 schedules starting verification test every three minutes. At any given time between 1 a.m. and 4 a.m. a maximum of one routing verification test will be running in the network, provided a test takes less than three minutes. The total load induced by all the sub-test will then be evenly spread between 1 a.m. and 4 a.m.