JP6042284B2 - TDM network system and scheduling method - Google Patents

Description

  The present invention relates to a method (scheduling method) for dynamically allocating time slots in a TDM network system using TDM (Time Division Multiplexing) technology.

  FIG. 35 shows an example of scheduling in the TDM network.

  As shown in FIG. 35, in the TDM network, each node performs a repeating operation in units of TDM frame length t, and a timing at which a data signal is transmitted between the nodes (referred to as a time slot (TS)). ) Is determined and operated in advance.

  In the TDM network, a common time slot is assigned to a transit link through which a certain path passes (for example, a common time slot S1 for links A to B and links B to C through which a path from node A to C passes). Assign). A path refers to a communication path that connects a source node and a destination node.

  In the TDM network, the same time slot cannot be used in the same link (for example, in the links B to C, the time slot S1 cannot be used for the path from the node B to the D).

  In order to perform efficient data transfer in the TDM network, it is necessary to assign time slots with as little gap as possible. Therefore, scheduling for determining the time slots to be assigned to each path is performed.

  Hereinafter, a table representing the allocation status of time slots defined on each link in the TDM network is referred to as a schedule table. The above-described scheduling is an operation of assigning paths on this schedule table.

  Here, as a conventional example of a scheduling method in a TDM network system, there are various heuristic methods. In many heuristic methods (for example, Non-Patent Document 1), time slots are assigned in order for each given topology and traffic.

  Further, the present inventors have developed a hierarchical system (non-patent document) in order to increase the scale of a TDM network system that dynamically allocates time slots in a TDM network according to communication traffic (for example, in the order of seconds or less). 2) and the Rip-up & Re-allocate method (Non-patent Document 3).

  FIG. 36 shows an example of the hierarchization method and the Rip-up & Re-allocate method.

  As shown in FIG. 36, the hierarchization method groups a plurality of nodes in a TDM network system and performs time slot allocation calculation in each group independently, thereby speeding up time slot allocation calculation. It is.

  The Rip-up & Re-allocate method is intended to speed up the time slot allocation calculation by making only the portion where traffic fluctuation occurs in the TDM network system as the target of the time slot allocation calculation.

K. Gokyu, K. Baba, and M. Murata, "Path accommodation methods for unidirectional rings with optical compression TDM," IEICE Transactions on Communications, vol. E83-B, pp. 2294-2303, Oct. 2000. Nakagawa, Hattori, Kimijima, Katayama, Misawa, Hiramatsu, “Proposal of Optical TDM Scheduling Method HOTS Using Hierarchy,” Society of Society Society Conference, B-6-25, September 2012 Nakagawa, Hattori, Kimijima, Katayama, Misawa, "Proposal of Rip-up & Re-allocate Dynamic Bandwidth Allocation Method Focusing on Traffic Fluctuation Difference in Optical L2 Switch Networks," IEICE General Conference, B-6-3, 2013 March

  FIG. 37 shows problems of the heuristic method (for example, Non-Patent Document 1) and the hierarchization method.

  As shown in FIG. 37, the heuristic method, for example, selects one path at a time in order from the path with the largest number of hops, searches for an empty time slot position in order from the youngest time slot position, and sets the found empty time slot position. Assign the selected path.

  However, the heuristic method cannot speed up the time slot allocation calculation in a large-scale TDM network system.

  On the other hand, in the hierarchical system, a plurality of nodes in the TDM network system are grouped and the time slot allocation calculation in each group is performed independently. Therefore, even in a large-scale TDM network system, the time slot allocation calculation is performed at high speed. Can be achieved.

  However, the hierarchization method secures extra time slots as a price for realizing high-speed time slot allocation calculation, as shown in FIG. 37, in order to ensure the exclusivity of time slot allocation in each group. Allocated time slots may not fit within the TDM frame length.

  As a result, traffic cannot be transferred as required in a TDM network system having the same installation amount.

  For this reason, in a TDM network system that performs time slot allocation in a hierarchical manner, increasing the amount of traffic transferred with the same amount of equipment has been an issue.

  This problem also applies to a TDM network system that performs time slot allocation by the Rip-up & Re-allocate method.

  Accordingly, an object of the present invention is to provide a technique capable of increasing the amount of traffic transferred with the same amount of equipment in a TDM network system.

The TDM network system of the present invention
In a TDM network system comprising a plurality of nodes, a link connecting the nodes, and a scheduler that assigns a time slot to each path connecting a source node and a destination node. ,
The scheduler
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. A computing device that allocates time slots and creates a schedule table that indicates the allocation status of the time slots for each path;
A memory for storing the schedule table,
The arithmetic unit is:
The allocated time slot on the schedule table is rearranged to an empty time slot position until a calculation abort trigger is received.

Another TDM network system of the present invention is:
In a TDM network system comprising a plurality of nodes, a link connecting the nodes, and a scheduler that assigns a time slot to each path connecting a source node and a destination node. ,
The scheduler
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. A computing device that allocates time slots and creates a schedule table that indicates the allocation status of the time slots for each path;
A memory for storing the schedule table,
The arithmetic unit is:
When the condition is satisfied, the allocated time slot on the schedule table is rearranged at an empty time slot position.

Still another TDM network system of the present invention is:
In a TDM network system comprising a plurality of nodes, a link connecting the nodes, and a scheduler that assigns a time slot to each path connecting a source node and a destination node. ,
The scheduler
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. A computing device that allocates time slots and creates a schedule table that indicates the allocation status of the time slots for each path;
A memory for storing the schedule table,
The arithmetic unit is:
When receiving a notice for rearranging time slots, the allocated time slots on the schedule table are rearranged at empty time slot positions.

The scheduling method of the present invention includes:
In a TDM network system, comprising: a plurality of nodes; a link that connects the nodes; and a scheduler that assigns a time slot to each path connecting the source node and the destination node. In the scheduling method,
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. Assign a time slot and create a schedule table that shows the time slot assignment status for each path.
Storing the schedule table in a memory;
The allocated time slot on the schedule table is rearranged to an empty time slot position until a calculation abort trigger is received.

  According to the present invention, the scheduler allocates a time slot to each path, creates a schedule table indicating the allocation status of the time slot, stores it in the memory, and assigns the allocated time slot on the schedule table to an empty time slot. Rearrange to position.

  Accordingly, since the allocated time slots can be accommodated within the range of the TDM frame length, the amount of traffic transferred with the same equipment amount can be increased in the TDM network system having the same equipment amount. can get.

It is a figure which shows the example of a structure of the TDM network system of the 1st Embodiment of this invention. It is a figure which shows the basic idea of the 1st Embodiment of this invention. It is a figure which shows the example of a structure of the scheduler 40 of the 1st Embodiment of this invention. It is a figure which shows the example of a structure of the node 10 of the 1st Embodiment of this invention. It is a figure which shows the example of a detailed structure of the scheduler 40 of the 1st Embodiment of this invention. It is a figure which shows the precondition of the operation | movement of the 1st Embodiment of this invention. It is a figure which shows the example of schematic operation | movement of the scheduler 40 of the 1st Embodiment of this invention. It is a figure which shows the example of the operation | movement sequence of the whole TDM network system of this invention. It is a figure which shows the example of the operation | movement flow of the scheduler 40 of the 1st Embodiment of this invention. It is a figure which shows the example of a specific operation | movement of the scheduler 40 of the 1st Embodiment of this invention. It is a figure which shows the example of a specific operation | movement of the scheduler 40 of the 1st Embodiment of this invention. It is a figure which shows the example of a detailed structure of the scheduler 40 of the 2nd Embodiment of this invention. It is a figure which shows the example of a detailed structure of the scheduler 40 of the 3rd Embodiment of this invention. It is a figure which shows the example of a detailed structure of the scheduler 40 of the 4th Embodiment of this invention. It is a figure which shows the example of a detailed structure of the scheduler 40 of the 5th Embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 6th Embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 7th Embodiment of this invention. It is a figure which shows the example of operation | movement of the scheduler 40 of the 8th Embodiment of this invention. It is a figure which shows the example of a detailed structure of the scheduler 40 of the 8th Embodiment of this invention. It is a figure which shows the example of operation | movement of the scheduler 40 of the 9th Embodiment of this invention. It is a figure which shows the example of a Rip-up & Re-allocate system. It is a figure which shows the image of the time flow of a Rip-up & Re-allocate process and a rearrange process. It is a figure which shows the example of the rearrange process in a Rip-up & Re-allocate process. It is a figure which shows the image of a missing tooth state. It is a figure which shows the example of a structure of the TDM network system of the 10th Embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 11th and 12th embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 13th and 14th embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 15th and 16th embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 17th and 18th embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 19th Embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 20th Embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 21st Embodiment of this invention. It is a figure which shows the example of a structure of the TDM network system of the 22nd Embodiment of this invention. It is a figure which shows the example of the method of increasing an adjacent time slot in a link direction, and the method of increasing an adjacent time slot in a time direction. It is a figure which shows the example of the scheduling in a TDM network. It is a figure which shows the prior art example of the scheduling in a TDM network. It is a figure which shows the subject of the prior art example of the scheduling in a TDM network.

EMBODIMENT OF THE INVENTION Below, the form for implementing this invention is demonstrated with reference to drawings.
(1) First Embodiment FIG. 1 shows an example of the configuration of a TDM network system according to this embodiment.

  As shown in FIG. 1, the TDM network system of this embodiment is a ring network system in which N (N is a natural number of 2 or more) nodes 10 are connected by links 20. In FIG. 1, N = 5, but the number of N is not limited to this.

  Each node 10 is connected to a host computer 30 and transfers data signals between the host computers 30.

  The scheduler 40 performs scheduling for assigning a time slot to each path on the TDM network system. The deployment location of the scheduler 40 is not limited to FIG. 1 and may be deployed to another node 10.

  FIG. 2 shows the basic idea of this embodiment.

  As shown in FIG. 2, the scheduler 40 first calculates a time slot assigned to each path at high speed by hierarchical calculation based on the conventional hierarchical method described in Non-Patent Document 2.

  After that, the scheduler 40 performs a process of rearranging (rearranged) the allocated time slots that have already been allocated to paths that do not fall within the TDM frame length range to empty time slot positions within the TDM frame length range. . This solves the problem that the allocated time slot exceeds the TDM frame length.

  At this time, the scheduler 40 repeats the rearrange process using the given calculation time of the time slot allocation as much as possible, thereby approaching the optimal solution for the time slot allocation.

  Here, the basic idea of this embodiment will be described in detail.

  The hierarchization method is based on the calculation time of time slot allocation in a large-scale TDM network system in the existing heuristic method, and has realized to increase the calculation time of time slot allocation.

  However, when viewed from the index of time slot allocation efficiency, the stratified method tends to be worse than the heuristic method.

  In other words, time slot allocation calculation time and allocation efficiency are generally in a trade-off relationship, and if the priority is given to shortening the calculation time in the hierarchization method, the allocation efficiency may deteriorate by 10% or more compared to the heuristic method. Arise.

  Therefore, when performing scheduling, it is considered effective to consider an index of time slot allocation allocation efficiency in addition to the TDM network system size and time slot allocation calculation time.

Hereinafter, according to Non-Patent Document 2, which will be described using numerical examples, when performing time slot allocation calculation in a ring network composed of 256 nodes, using a hierarchization method, the calculation is compared with the existing heuristic method. While the time can be reduced to 1/200, the allocation efficiency of time slot allocation is deteriorated by 10%.

  The main reason why the allocation efficiency of time slot allocation deteriorates by 10% is to secure an extra time slot for hierarchization (ensure the exclusivity of allocation).

  However, the calculation time itself of time slot allocation can be greatly reduced.

  Therefore, in the present embodiment, processing for increasing allocation efficiency is added in exchange for a slight increase in calculation time. This processing is the rearrange processing of the time slots described in FIG. 2 (processing for filling the allocated time slots in the reserved empty time slot positions).

  The target of the rearrange processing is a path that does not fit in the TDM frame length (about 10% of all paths that do not fit in the TDM frame length for the amount of resources required when optimal allocation is performed) Even if all assigned time slots assigned to such paths are rearranged, assignment is completed in a time shorter than the time required for assigning time slots to all paths by the heuristic method (the above-mentioned example). In this case, the rearrangement is completed in about 10% time).

  As a result, it is possible to achieve an allocation efficiency equivalent to that of the heuristic method in exchange for an increase in calculation time of about 10% at the maximum of the time required to calculate time slot allocation to all paths by the heuristic method.

  Also, if there is a restriction on the time slot assignment calculation time (for example, the calculation is completed within 1 second), the rearrangement process is repeated within the time limit so that the time restriction is maintained and the efficiency with high assignment efficiency is maintained. Operation becomes possible.

  Also, if there is a restriction on the allocation efficiency of time slot allocation (for example, the allocation efficiency is 95% or more), the rearrange process is repeated until the allocation efficiency exceeds the threshold value, while ensuring the transfer efficiency while calculating. Time can be reduced.

  Therefore, it is necessary to have logic to execute the rearrange process and logic to abort the rearrange process. By using these logics, the rearrange process is repeated using the given calculation time to optimize the time slot allocation. Approach the solution.

  FIG. 3 shows an example of the configuration of the scheduler 40 of the present embodiment.

  As illustrated in FIG. 3, the scheduler 40 according to the present embodiment includes an IO unit 401, an arithmetic device 402, and a memory 403.

  Table 1 shows the contents of the input, the processing when there is the input, and the contents of the output in each part shown in FIG.

  Note that the arithmetic device 402 of the present embodiment additionally performs time slot rearrangement processing in addition to the processing described in Table 1, and performs this rearrangement processing in combination with a hierarchization method (hereinafter referred to as a “hierarchical method”). The same in the second to ninth embodiments). A detailed configuration of the scheduler 40 of this embodiment will be described with reference to FIG.

  FIG. 4 shows an example of the configuration of the node 10 of this embodiment.

  As shown in FIG. 4, the node 10 of this embodiment includes a controller 101, a switch 102, a transmission unit (Tx) 103, a reception unit (Rx) 104, a buffer 105, and an IO unit 106. doing.

  Table 2 shows the contents of the input, the processing when there is the input, and the contents of the output in each part shown in FIG.

  FIG. 5 shows an example of a detailed configuration of the scheduler 40 of the present embodiment.

  As shown in FIG. 5, the scheduler 40 of this embodiment includes an IO unit 401, a traffic information holding unit 404, a node grouper 405, an intra-group schedule calculation unit 406, an intra-group schedule table holding unit 407, and an inter-group Schedule calculation unit 408, inter-group schedule table holding unit 409, virtual schedule table calculation unit 410, abort timer 411, calculation abort notification unit 412, TS rearrangement allocation calculator 413, and actual schedule table calculator 414 And an actual schedule table holding unit 415 and a node control signal generation unit 416.

  In FIG. 5, a node grouper 405, an intra-group schedule calculation unit 406, an inter-group schedule calculation unit 408, a virtual schedule table calculation unit 410, an abort timer 411, a calculation abort notification unit 412, a TS rearrangement allocation calculator 413, an actual schedule The table calculation unit 414 and the node control signal generation unit 416 correspond to the arithmetic device 402 shown in FIG. 3, and the traffic information holding unit 404, the intra-group schedule table holding unit 407, the inter-group schedule table holding unit 409, and the real The schedule table holding unit 415 corresponds to the memory 403 illustrated in FIG.

  In FIG. 5, a virtual schedule table calculation unit 410, an abort timer 411, a calculation abort notification unit 412, a TS rearrangement allocation calculation unit 413, and an actual schedule table calculation unit 414 are added from the conventional scheduler.

  The IO unit 401 receives from each node 10 traffic information indicating the traffic amount requested by each path having the node 10 as a transmission source node.

  The traffic information holding unit 404 holds the traffic information received by the IO unit 401.

  The node grouper 405 groups the N nodes 10 based on the traffic information held in the traffic information holding unit 404 and notifies the intra-group schedule calculation unit 406 and the inter-group schedule calculation unit 408 of the group combination status. To do.

  Based on the traffic information held by the traffic information holding unit 404, the intra-group schedule calculation unit 406 determines whether the nodes 10 in the group (between the nodes 10 belonging to the same group or between the nodes 10 belonging to different groups). In-group scheduling is performed, and time slot allocation is performed between nodes 10 in the group based on the time slot allocation result.

  The intra-group schedule table holding unit 407 holds the intra-group schedule table calculated by the intra-group schedule calculation unit 406.

  The inter-group schedule calculation unit 408 allocates time slots between groups (including both the same group and different groups) based on the traffic information held in the traffic information holding unit 404. Scheduling is performed, and based on the time slot allocation result, an inter-group schedule table representing the time slot allocation status between groups is calculated.

  The inter-group schedule table holding unit 409 holds the inter-group schedule table calculated by the inter-group schedule calculation unit 408.

  The virtual schedule table calculation unit 410 uses the intra-group schedule table (the scheduling result within the group) held by the intra-group schedule table holding unit 407 as the inter-group schedule table ( By substituting it into the scheduling result between groups), a virtual schedule table representing the time slot allocation status on each link 20 is calculated.

  When the abort timer 411 times out, the calculation abort notification unit 412 notifies the TS rearrangement allocation calculation unit 413 that the time slot allocation calculation is aborted.

  The TS rearrangement allocation calculation unit 413 has the TDM frame length of the paths on the virtual schedule table calculated by the virtual schedule table calculation unit 410 until a notification of calculation termination is received from the TS rearrangement allocation calculation unit 413. For a path that does not fall within the range, the process of rearranging (rearranged) the allocated time slots assigned to the path to empty time slot positions within the TDM frame length range is repeated.

  The actual schedule table calculation unit 414 allocates the time slots on each link 20 based on the allocation result of the time slots after the rearrangement processing is performed on the virtual schedule table in the TS rearrangement allocation calculation unit 413. An actual schedule table representing the situation is calculated.

  The actual schedule table holding unit 415 holds the actual schedule table calculated by the actual schedule table calculating unit 414.

  The node control signal generation unit 416 converts the node processing (route switching, data signal transfer, etc.) of each node 10 based on the actual schedule table held by the actual schedule table holding unit 415, and converts each node 10 A control signal representing the schedule table is generated.

  The IO unit 401 transmits the control signal generated by the node control signal generation unit 416 to each node 10.

  Hereinafter, the operation of this embodiment will be described.

  FIG. 6 shows preconditions for the operation of this embodiment.

  As shown in FIG. 6, here, for convenience of explanation, the TDM network system has a one-way ring configuration with N = 6, and one channel that can be simultaneously connected to the same slot per link (fiber multiplexing or wavelength). No multiplexing is performed). The six nodes 10 are assumed to be nodes 10-1 to 10-6, respectively. However, the present invention is not limited to this, and can also be applied to a case where an arbitrary topology and wavelength multiplexing are performed including a bidirectional ring (a schedule table is created for each wavelength of each fiber).

  FIG. 7 shows an example of a schematic operation of the scheduler 40.

  As shown in FIG. 7, first, in step i, the scheduler 40 (arithmetic device 402) assigns time slots to each path by hierarchical calculation based on the conventional hierarchical system. At this time, a path may be temporarily allocated in a range exceeding the TDM frame length.

  Next, in step ii, the scheduler 40 (computing device 402) rearranges allocated time slots that do not fall within the TDM frame length range to rearranged time slot positions within the TDM frame length range (rear range). Repeat the process.

  Thereafter, in step iii, when the scheduler 40 (computing device 402) detects a calculation abort trigger notified at a period of a fixed time interval T (timeout time of the abort timer 411), an allocated range exceeding the TDM frame length has been allocated. The time slot is truncated, and the result is transmitted to each node 10 as a control signal.

  FIG. 8 shows an example of an operation sequence of the entire TDM network system. In FIG. 8, the host computer connected to the node 10-1 is 30-1, and the host computer connected to the node 10-2 is 30-2.

  As shown in FIG. 8, in steps S101 and S102, the host computer 30-1 connected to the node 10-1 sends a data signal addressed to the host computer 30-2 connected to the node 10-2 to the node 1. Suppose you send it.

  Then, in step S103, the node 10-1 buffers the data signal received from the host computer 30-1, and the traffic requested by the path from the node 10-1 to the node 10-2 for transmission of the data signal. Monitor the amount.

  Next, in step S104, the node 10-1 transmits to the scheduler 40 traffic information indicating the traffic amount (including the traffic amount monitored above) requested by each path having the node 10-1 as a transmission source. Transmission of traffic information is performed periodically regardless of the presence or absence of a data signal. Therefore, in step S105, the node 10-2 also transmits traffic information to the scheduler 40.

  Next, in steps S106, S107, and S108, the scheduler 40 performs scheduling based on the traffic information, and transmits a control signal indicating the node processing schedule of the node to each of the nodes 10-1 and 10-2. To do.

  Thereafter, in steps S109, S110, and S111, each of the nodes 10-1 and 10-2 transfers the data signal to the host computer 30-2 according to the schedule represented by the control signal.

  In the TDM network system, the operation sequence of FIG. 8 is repeatedly performed.

  FIG. 9 shows an example of the operation flow of the scheduler 40.

  As shown in FIG. 9, in step S201, the scheduler 40 (arithmetic unit 402) sums up the traffic volume requested by each path and then calculates the time required for each path based on the traffic volume requested by each path. The number of slots is calculated, and this is set as the required number of time slots.

  Next, in step S202, the scheduler 40 (arithmetic device 402) assigns a time slot to each path based on the required number of time slots for each path, and calculates an actual schedule table.

  Thereafter, in step S203, the scheduler 40 (arithmetic device 402) converts the node processing of each node based on the actual schedule table. The node processing schedule of each node 10 is notified from the scheduler 40 to each node.

  Here, the operation of step S202 will be described in detail.

  In the hierarchization calculation based on the conventional hierarchization method, first, in step S204, time slots are assigned to paths between the nodes 10 in the group to calculate an intra-group schedule table, and then in step S205, each group is calculated. An inter-group schedule table is calculated by assigning time slots between them, and then, in step S206, the intra-group schedule table is substituted into the inter-group schedule table, and the resulting schedule table is used as the actual schedule table. .

  On the other hand, in the present embodiment, the schedule table obtained in step S206 is used as a virtual schedule table, and thereafter the TDM frame length of the path on the virtual schedule table is notified until a calculation abort notification is received in step S207. The process (step S208) of rearranging (rearranged) the assigned time slots assigned to paths that are not within the range to empty time slot positions within the range of the TDM frame length is repeated. If a calculation abort notification is received in step S207, the assigned time slot in the range exceeding the TDM frame length is discarded, and the schedule table is used as the actual schedule table.

  10 and 11 show examples of specific operations of the scheduler 40. FIG. 10 shows the operation until the virtual schedule table calculation unit 410 calculates the virtual schedule table, and FIG. 11 shows the subsequent operation.

  As shown in FIG. 10, first, the node grouper 405 logically bundles six nodes 10-1 to 10-6. Here, as an example, nodes 10-1 to 10-6 are grouped into three groups of two nodes, nodes 10-1 and 10-2 are group A, and nodes 10-3 and 10-4 are group B. The nodes 10-5 and 10-6 are bundled into the group C. The node grouper 405 holds information on the group combination status and notifies the intra-group schedule calculation unit 406 and the inter-group schedule calculation unit 408 of this.

  Next, the intra-group schedule calculation unit 406 assigns time slots to paths between nodes in the group (including both nodes belonging to the same group and nodes belonging to different groups). Here, as an example, the time slots selected in ascending order of the time slot positions are assigned to the paths selected in descending order of the path length. Specifically, the time slot with the youngest time slot position is assigned to the path of node 1 → node 6 with the longest path length. The time slot allocation result is held in the in-group schedule table holding unit 407 as an in-group schedule table.

  Next, the inter-group schedule calculation unit 408 allocates time slots between the groups (including both the same group and different groups). Here, only the avoidance of time slot collision is considered, and the restriction on the TDM frame length may be ignored. The time slot allocation result is held in the inter-group schedule table holding unit 409 as an inter-group schedule table.

  Next, the virtual schedule table calculation unit 410 calculates the virtual schedule table by substituting the intra-group schedule table into the inter-group schedule table. At this time, a path may be assigned to a time slot position exceeding the TDM frame length.

  As shown in FIG. 11, next, the TS rearrangement allocation calculating unit 413 converts time slots allocated to paths that do not fall within the range of the TDM frame length among paths on the virtual schedule table to the TDM frame length. Rearrange (rearrange) to an empty time slot position within the range. Here, as an example, the assigned time slot assigned to the oldest time slot position is moved to the youngest time slot position among the empty time slot positions within the TDM frame length range. This rearrangement process is repeated until there is a notification of calculation termination.

  Here, when the TS relocation allocation calculation unit 413 repeats the rearrangement process and the abort timer 411 times out (T interval), the calculation abort notification unit 412 cancels the calculation of the time slot allocation calculation by the TS rearrangement. Notifying the allocation calculation unit 413, and receiving this, the TS rearrangement allocation calculation unit 413 aborts the calculation of the rearrange processing.

  Thereafter, the actual schedule table calculation unit 414 truncates the allocated time slots in the range exceeding the TDM frame length, and sets the schedule table as the actual schedule table. In the example of FIG. 11, since the assigned time slot assigned to the path from the node 10-3 to the node 10-5 is discarded, the assignment of the time slot to the path from the node 10-3 to the node 10-5 is failed. Become.

  Note that the rearrangement process shown in FIG. 11 is an example, and the present invention is not limited to this.

  For example, in the example of FIG. 11, the rearrange processing is performed from the path assigned to the oldest time slot position on the virtual schedule table. For example, the arrangement processing may be any one of those shown in Table 3.

  In the example of FIG. 11, the time slots are moved in descending order of the time slot positions allocated on the virtual schedule table. However, the order of moving the time slots (which time slot is moved) is as follows: For example, any of Table 4 may be used.

  In the example of FIG. 11, the allocated time slot is moved to the youngest time slot position among the empty time slot positions within the range of the TDM frame length. For example, any one of Table 5 may be used.

  As described above, in the present embodiment, the scheduler 40 performs the layered calculation based on the conventional layered method, and then assigns the assigned time slot assigned to the path that does not fall within the TDM frame length range. Rearrange (rearrange) to empty time slot positions within the range of the TDM frame length.

  Therefore, since the allocated time slot can be accommodated within the range of the TDM frame length, it is possible to increase the amount of traffic transferred with the same equipment amount in the TDM network system having the same equipment amount.

In the present embodiment, the scheduler 40 aborts the calculation of the time slot allocation by the abort timer 411. Therefore, even when the calculation time of the time slot allocation is limited, the time constraint can be maintained. can get.
(2) Second Embodiment FIG. 12 shows an example of a detailed configuration of the scheduler 40 of this embodiment.

  As shown in FIG. 12, the scheduler 40 of this embodiment has the same components as the configuration of the first embodiment shown in FIG. However, the TS rearrangement allocation calculation unit 413 inputs not only the virtual schedule table calculated by the virtual schedule table calculation unit 410 but also the inter-group schedule table held by the inter-group schedule table holding unit 409. The point is different.

  The TS rearrangement allocation calculation unit 413 uses an inter-group schedule table when calculating rearrangement processing.

As described above, in the present embodiment, the scheduler 40 uses the inter-group schedule table when calculating the rearrangement process to further search for an empty time slot position to which the allocated time slot is to be moved. The effect that it becomes easy is acquired.
(3) Third Embodiment In the first and second embodiments, a timer (an abort timer 411) is provided in the scheduler 40.

  On the other hand, in this embodiment, an abort timer is provided outside the scheduler 40.

  FIG. 13 shows an example of a detailed configuration of the scheduler 40 of the present embodiment.

  As shown in FIG. 13, the scheduler 40 of the present embodiment is different from the configuration of the first embodiment shown in FIG. 5 in that an abort instruction detection unit 417 is provided instead of the abort timer 411. .

  The abort instruction detection unit 417 is connected to a timer provided outside the scheduler 40. When the timer times out, the abort instruction detection unit 417 notifies the calculation abort notification unit 412 that an instruction to abort the calculation of time slot allocation has been detected.

As described above, in this embodiment, since the timer is provided outside the scheduler 40, there is an effect that it is possible to manually set the period T for notifying time slot allocation calculation termination.
(4) Fourth Embodiment In the first to third embodiments, the scheduler 40 aborts the calculation of time slot allocation by a timer.

  On the other hand, in the present embodiment, in addition to the time slot allocation calculation abortion by the timer, the calculation is aborted depending on the situation of the virtual schedule table.

  In FIG. 14, the example of a structure of the scheduler 40 of this embodiment is shown.

  As shown in FIG. 14, the scheduler 40 of this embodiment is different from the configuration of the first embodiment shown in FIG. 5 in that a virtual schedule table monitoring unit 418 is additionally provided.

  The virtual schedule table monitoring unit 418 monitors the virtual schedule table, and when the schedule length of the virtual schedule table becomes equal to or less than the TDM frame length, notifies the calculation abort notification unit 412 of a trigger for the calculation abort of time slot allocation.

  Here, the schedule length is the minimum number of time slots required when performing the TDM operation according to the schedule table.

  When the schedule length is equal to or shorter than the TDM frame length, all time slots can be accommodated within the range of the TDM frame length, and it is not necessary to continue the calculation of the rearrange processing. Therefore, in such a case, the time slot allocation calculation time can be further shortened by aborting the time slot allocation calculation.

As described above, in the present embodiment, when the schedule length becomes equal to or shorter than the TDM frame length, the scheduler 40 aborts the calculation of the time slot allocation, so that the calculation time of the time slot allocation is further shortened. The effect of being able to be obtained.
(5) Fifth Embodiment In the present embodiment, in the same way as the fourth embodiment, in addition to the time slot allocation by the timer, the calculation is aborted depending on the status of the virtual schedule table.

  FIG. 15 shows an example of the configuration of the scheduler 40 of this embodiment.

  As shown in FIG. 15, the scheduler 40 of this embodiment is different from the configuration of the first embodiment shown in FIG. 5 in that an allocation path monitoring unit 419 is additionally provided.

  The required allocation path monitoring unit 419 monitors the virtual schedule table, stores the paths allocated to the time slot positions exceeding the TDM frame length on the virtual schedule table in a list format, and the range of the TDM frame length by the rearrange processing A path whose assigned position is changed is excluded from the list.

  Then, when the list becomes empty, the required allocation path monitoring unit 419 gives the calculation abort notification unit 412 a trigger for time slot allocation calculation abort.

  When the list becomes empty, all time slots can be accommodated within the range of the TDM frame length. In such a case, it is not necessary to continue the calculation of the rearrange processing. Therefore, in such a case, the time slot allocation calculation time can be further shortened by aborting the time slot allocation calculation.

As described above, in the present embodiment, the scheduler 40 aborts the calculation of the time slot allocation when the list becomes empty, so that the calculation time of the time slot allocation can be further shortened. Is obtained.
(6) Sixth Embodiment In the first to third embodiments, the scheduler 40 aborts the calculation of time slot allocation by a timer.

  On the other hand, in this embodiment, the controller 101 arranged in one of all the nodes 10 controls the time system, and the controller 101 triggers the scheduler 40 to abort the calculation of time slot allocation. Notice.

  FIG. 16 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 16, in the TDM network system of the present embodiment, the controller 101 (referred to as the parent controller 101-1) deployed in one node 10 (referred to as the node 10-1) becomes the parent, and the others. A parent-child relationship is established with a controller 101 (referred to as child controllers 101-2 to 101-5) provided in the node 10 (referred to as nodes 10-2 to 10-5).

  The parent controller 101-1 manages the time system in the TDM network system, and synchronizes by transmitting control signals to the other nodes 10-2 to 10-5.

  Further, the parent controller 101-1 periodically gives the scheduler 40 a trigger for aborting the calculation of time slot allocation.

  The scheduler 40 is deployed in the node 10-1 where the parent controller 101-1 is deployed.

  As described above, in the present embodiment, one node 10 in which the parent controller 101-1 is deployed periodically gives a trigger for time slot allocation calculation termination to the scheduler 40.

  Therefore, the effect that the calculation of the time slot allocation can be aborted at the initiative of the node 10 can be obtained.

In this embodiment, it is possible to eliminate the time slot allocation calculation by the abort timer 411 provided in the scheduler 40. In this case, the abort timer 411 can be deleted.
(7) Seventh Embodiment In the first to third embodiments, the scheduler 40 aborts the calculation of time slot allocation by a timer.

  On the other hand, in the present embodiment, the calculation of time slot allocation is aborted by receiving a predetermined number of traffic information from each node 10 as a trigger.

  FIG. 17 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 17, in the TDM network system of this embodiment, the scheduler 40 is different from the configuration of the first embodiment shown in FIG. 3 in that a control signal counter 420 is additionally provided. .

  The control signal counter 420 counts the number of received control signals for reporting traffic information from each node 10, and when the counter value reaches a threshold value, triggers the calculation unit 402 to abort the calculation of time slot allocation. And clear the counter value.

  As a variation of the present embodiment, a method of counting the number of time slots when a control signal is also transmitted in a TDM time slot can be considered.

  It is also effective to attach an ID to the control signal transmitted by each node 10 in order to detect the loss of the control signal.

  In this embodiment, it is possible to eliminate the time slot allocation calculation by the abort timer 411 provided in the scheduler 40. In this case, the abort timer 411 can be deleted.

As described above, in the first to seventh embodiments, several triggers for aborting the calculation of the rearrange processing (time slot allocation) have been described. However, these triggers may be applied independently or 2 You may apply combining two or more.
(8) Eighth Embodiment In the first to seventh embodiments, it is assumed that the TDM network system has a one-way ring configuration.

  On the other hand, in the present embodiment, it is assumed that the TDM network system has a bidirectional ring configuration.

  When the present invention is applied to the configuration of the bidirectional ring, means for creating an actual schedule table for clockwise rotation and means for creating an actual schedule table for counterclockwise rotation are required. 19

  FIG. 18 shows an example of the operation of the scheduler 40 of this embodiment. In FIG. 18, N = 7, and the seven nodes 10 are designated as nodes 10-1 to 10-7, respectively.

  As shown in FIG. 18, first, the scheduler 40 logically bundles seven nodes 10-1 to 10-7. Here, as an example, the nodes 10-1 to 10-3 are bundled into the group A, the nodes 10-4 and 10-5 are bundled into the group B, and the nodes 10-6 and 10-7 are bundled into the group C.

  Next, the scheduler 40 assigns time slots to paths between nodes in the group (including both nodes belonging to the same group and nodes belonging to different groups).

  Next, the scheduler 40 allocates time slots between groups (including both the same group and different groups) separately for clockwise and counterclockwise use.

  At this time, time slot allocation may be performed in a detour.

  In FIG. 18, for example, when considering the path of the node 10-6 → 10-3, the shortest hop route is three hops counterclockwise. However, in the time slot allocation between groups, since the time slot allocation is performed in the clockwise direction from the group C → A, the clockwise path is also set in the nodes 10-3 → 10-6, resulting in 4 hops. .

  Therefore, if the number of hops in each of the clockwise and counterclockwise routes is known during the rearrange processing of the time slot, the node 10-6 → 10-3 is assigned to the path on the clockwise virtual schedule table. The time slots can be rearranged and rerouted to the time slot positions assigned to the nodes 10-3 → 10-6 on the counterclockwise virtual schedule table. Thus, using a route with a small number of hops is more effective in terms of required resource suppression.

  FIG. 19 shows an example of a detailed configuration of the scheduler 40 of the present embodiment.

  As shown in FIG. 19, the scheduler 40 of this embodiment adds a group traffic information holding unit 421 and a group route information holding unit 422 to the first embodiment shown in FIG. The components from the calculation unit 408 to the actual schedule 415 are provided for clockwise rotation and counterclockwise rotation, respectively.

  Specifically, for clockwise rotation, an inter-group schedule calculation unit 408-1, an inter-group schedule table holding unit 409-1, a virtual schedule table calculation unit 410-1, and a TS rearrangement allocation calculation unit 413-1 And an actual schedule table calculation unit 414-1 and an actual schedule table holding unit 415-1, and for counterclockwise use, an inter-group schedule calculation unit 408-2, an inter-group schedule table holding unit 409-2, A virtual schedule table calculation unit 410-2, a TS rearrangement allocation calculation unit 413-2, an actual schedule table calculation unit 414-2, and an actual schedule table holding unit 415-2.

  The group traffic information holding unit 421 holds traffic information of each group, and the group route information holding unit 422 holds route information such as the number of hops of the clockwise and counterclockwise routes of each group.

  The TS rearrangement allocation calculation units 413-1 and 413-2 use the route information held in the group route information holding unit 422 for the rearrangement process.

As described above, in the present embodiment, there is an effect that the present invention can be applied even when the TDM network system has a bidirectional ring configuration.
(9) Ninth Embodiment In the first to eighth embodiments, it is assumed that the number of ring stages of the TDM network system is one.

  On the other hand, in this embodiment, it is assumed that the TDM network system has a multistage ring configuration.

  FIG. 20 shows an example of the operation of the scheduler 40 of this embodiment. In FIG. 20, it is assumed that the number of ring stages is two and three lower rings A, B, and C are connected to the upper ring.

  As shown in FIG. 20, in the case of a multistage ring configuration, the scheduler 40 performs the scheduling between each ring and the scheduling within each ring in a hierarchical system, and then rearranges (rearranges) the time slots. Process.

  Specifically, the scheduler 40 bundles the lower rings A, B, and C into one group. That is, the nodes A, F, and G constituting the lower ring A belong to the group RA, the nodes B, H, I, and J constituting the lower ring B to the group RB, and the nodes C, K, and L constituting the lower ring C. , M bind to group RC. Nodes E and D are group Z.

  Next, the scheduler 40 performs scheduling between the rings and scheduling within each ring.

  In the case of a multistage ring, the scheduler 40 holds a schedule table for each lower ring.

  Therefore, the scheduler 40 calculates the rearrangement process while simultaneously considering the upper ring schedule table and the lower ring schedule table.

As described above, in the present embodiment, there is an effect that the present invention can be applied even when the TDM network system has a multistage ring configuration.
(10) Tenth Embodiment In the first to ninth embodiments, the rearrangement processing of time slots is combined with the hierarchization method described in Non-Patent Document 2.

  However, the present invention is not limited to this, and it is also possible to combine the rearrange processing of time slots with the Rip-up & Re-allocate method described in Non-Patent Document 3.

  This embodiment and the following embodiments are embodiments in which the rearrange processing of time slots is applied to the Rip-up & Re-allocate method.

  First, the Rip-up & Re-allocate method will be briefly described.

  FIG. 21 shows an example of the Rip-up & Re-allocate method.

  The Rip-up & Re-allocate method does not recalculate time slot allocation on a zero basis, but recalculates only portions where traffic fluctuations occur in the TDM network system.

  In the recalculation of the time slot allocation, the previous time slot allocation (schedule table) is changed to make it asymptotic to the optimal solution quickly.

  At that time, for each path (ground), first, the difference in traffic volume between the previous scheduling execution time and the current scheduling execution time is calculated, and the traffic volume is greatly reduced and the number of required time slots is reduced. For, the number of time slots assigned to the path is decreased (this process removes the time slot from the schedule table (Rip-up process)), the traffic volume greatly increases and the number of required time slots increases. For the pass, an additional time slot is assigned at an empty time slot position (this process is a pasting process for adding a time slot in the schedule table (Re-allocate process)).

  In the example of FIG. 21, the situation changes from a situation where the traffic amount of the path for the node A is large to a situation where the traffic amount of the path for the node B is large.

  In this case, if the number of time slots assigned to the paths for Node A and Node B is left as they are, the time slots for the path for Node A will remain, and the time slots for the path for Node B will be insufficient. Therefore, the time slot allocation efficiency is inefficient.

  Therefore, an attempt is made to delete the remaining time slot in the path for node A, and additionally assign it to the path for node B having a short time slot (Rip-up & Re-allocate). This operation is performed for all nodes.

  In the Rip-up & Re-allocate method, the calculation time increases with an increase in the number of Rip-up & Re-allocate to be executed (the number of target paths), but the inefficiency is improved.

  Therefore, in order to suppress an increase in calculation time, it is sufficient that the inefficiency is significantly improved with a small number of Rip-up & Re-allocate.

  By the way, in the Rip-up & Re-allocate method, it is also possible to perform the rearrange process during the Rip-up & Re-allocate process.

  FIG. 22 shows an image of the time flow of Rip-up & Re-allocate processing and rearrange processing.

  As shown in FIG. 22, it is possible to perform Rip-up & Re-allocate processing at the control cycle T and perform rearrange processing during the processing.

When combining the Rip-up & Re-allocate method with the time slot rearrangement, the following three cases cause deviation from the optimal solution of the time slot allocation, and thus correction is performed by the rearrangement process.
(I) When the schedule table is in a missing state due to Rip-up If the schedule table becomes in a missing state (state where free areas are divided) as a result of Rip-up, time slot allocation is performed later. It becomes difficult to add.

Therefore, garbage collection (concatenation of empty areas to make it easy to allocate later) is performed by rearrange processing.
(Ii) When the schedule table becomes missing due to Re-allocation When the schedule table becomes the same as (i) as a result of the re-allocation, the garbage collection is performed by the rearrange processing as in (i). Do.
(Iii) When re-allocation cannot be performed as it is, when there is no space to re-allocate and re-allocation cannot be performed as it is, rearrange processing is executed to create an empty band for a path to which a time slot is added.

  FIG. 23 shows an example of rearrange processing in the case of (iii).

  As shown in FIG. 23, for example, it is assumed that two continuous time slots are additionally allocated to the path from node A to node E. However, there is no empty time slot position to re-allocate as it is.

  Therefore, rearrange processing is executed to create a free band. This makes it possible to additionally allocate two consecutive time slots to the path from node A to node E.

Here, the following can be considered as variations of the method in which the rearrange processing of the time slot is combined with the Rip-up & Re-allocate method.
(1) Perform rearrange processing using the remainder of the calculation time This method executes the rearrange processing using the remainder of the calculation time of the time slot allocation after the Rip-up & Re-allocate processing. This can be implemented by adding a timer or the like for notifying calculation termination as in the first to ninth embodiments.
(2) Applying correction by rearrange processing in the middle of calculation This method applies correction by rearrange processing in the middle of calculation of Rip-up & Re-allocate processing, and requires a function to detect the deviation from the optimal solution. become.

  Table 6 shows actions when a monitoring subject, a monitoring target, a detection target, and a detection target are detected in this method.

  In Table 6, “tooth missing state” is a state in which vacant space is sparse on the schedule table and causes a deviation from the optimal solution, and whether or not the tooth missing state is a threshold value. Judge by comparison with. The detailed definition of “tooth missing state” will be described with reference to FIG.

“Accuracy” is the accuracy of time slot allocation for each path calculated from the relationship between the number of assigned time slots for each path and the traffic volume, and is determined by comparison with a threshold value.
(3) Upon receiving the trigger notification, the correction is performed by the rearrange processing (the normal Rip-up & Re-allocate processing is executed until the notification is received).
This method receives a notification of a trigger for performing the rearrange processing and performs correction by the rearrange processing, performs condition determination for executing the rearrange processing, and dynamically performs the rearrange processing.

  Table 7 shows actions when a monitoring subject, a monitoring target, a detection target, and a detection target are detected in this method.

  Here, the definition of the missing tooth state will be described.

  The missing tooth state qualitatively refers to a state in which the time slot allocation state is poor and there are many empty spaces in the schedule table.

  Further, the missing tooth state quantitatively means a state where the efficiency value Eff representing the clogged state of the assigned time slot on the schedule table defined by the following formula 1 is less than the threshold value Thr (Eff). say.

  In Equation 1, Link represents the number of links in the TDM network system, l represents a link number, is in the range of 1 to Link, and Alloc (l) is the time allocated on the link l. This represents the number of slots, and S represents the schedule length (the oldest time slot number assigned on the schedule table).

  Moreover, the setting example of threshold value Thr (Eff) is 50%, 70% etc., for example.

  In the state where fine vacancies are scattered on the schedule table, it becomes difficult to assign a time slot to a long path, and the allocation efficiency of the time slot is lowered.

  In other words, when the schedule table is in a missing state, the transfer efficiency is lowered and the accommodation traffic amount is lowered.

  FIG. 24 shows an image of a missing tooth state. In FIG. 24, it is assumed that the threshold value Thr (Eff) is set to 70%.

  As shown in FIG. 24, in the example on the left side, the efficiency value Eff is 77.1%, which is equal to or greater than the threshold value Thr (Eff), so that it is determined that the tooth missing state is not present.

  On the other hand, in the example on the right side, the efficiency value Eff is 60%, which is less than the threshold value Thr (Eff), so it is determined that the tooth is missing.

  As described above, there are some variations in the method in which the rearrange processing of the time slot is combined with the Rip-up & Re-allocate method.

  The present embodiment corresponds to (1) the method of executing the rearrange process using the remainder of the calculation time.

  FIG. 25 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 25, in the TDM network system of the present embodiment, the scheduler 40 is different from the configuration of the first embodiment shown in FIG. 3 in that an abort timer 423 is additionally provided.

  Note that the arithmetic device 402 of the present embodiment additionally performs time slot rearrangement processing in addition to the processing described in Table 1. Unlike the first to tenth embodiments, this rearrangement is performed. Processing is performed in combination with the Rip-up & Re-allocate method described with reference to FIG. 21 (the same applies to the following 11th to 22nd embodiments).

  The abort timer 423 periodically notifies the arithmetic unit 402 of a calculation abort trigger for time slot allocation.

  After the Rip-up & Re-allocate process, the arithmetic unit 402 uses the remainder of the time slot allocation calculation time, and repeats the process of rearranging (rearranging) the time slots until a calculation abort notification is received.

  As described above, in the present embodiment, the scheduler 40 performs the rearrange processing of the time slot after calculating the conventional Rip-up & Re-allocate processing.

  Therefore, since it is possible to avoid the schedule table from being in a missing state, etc., it is possible to increase the amount of traffic transferred with the same equipment amount in the TDM network system having the same equipment amount.

In the present embodiment, the scheduler 40 aborts the calculation of the time slot allocation by the abort timer 423, so that the time constraint can be maintained even when the calculation time of the time slot allocation is limited. can get.
(11) Eleventh Embodiment This embodiment is a method for performing correction by rearrange processing in the middle of calculation described in the tenth embodiment, and is shown in Table 6 [1]. It corresponds to.

  FIG. 26 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 26, in the TDM network system of the present embodiment, the scheduler 40 has the same components as the configuration of the first embodiment shown in FIG. The difference is that a table monitoring process is added to.

  The calculation CPU that performs time slot allocation calculation in the computing device 402 monitors the schedule table obtained by the Rip-up & Re-allocate process while calculating the Rip-up & Re-allocate process.

  The calculation CPU detects that the schedule table is in the tooth missing state by the method based on the threshold comparison described with reference to FIG.

  When the calculation CPU detects that the schedule table is in a missing state during the calculation of the Rip-up & Re-allocate process, the calculation CPU performs the rearrange process of the time slot.

  As described above, in the present embodiment, the scheduler 40 performs the rearrange processing of the time slot when the schedule table is in a missing state during the calculation of the Rip-up & Re-allocate processing.

Therefore, since it is possible to avoid the schedule table being in a missing state, it is possible to increase the amount of traffic transferred with the same equipment amount in the TDM network system having the same equipment amount.
(12) Twelfth Embodiment This embodiment is a method of performing correction by rearrange processing in the middle of calculation described in the tenth embodiment, and is shown in Table 6 [2]. It corresponds to.

  The configuration of this embodiment is the same as that of the eleventh embodiment, but the monitoring target and detection target of the computing device 402 are different.

  That is, the calculation CPU that performs time slot allocation calculation in the arithmetic device 402 performs the Rip-up & Re-allocate processing while calculating the traffic amount requested by each path and the Rip-up & Re-allocate processing. The number of assigned time slots assigned to each path is monitored on the obtained schedule table.

  The calculation CPU detects that there is a path whose time slot allocation accuracy has deteriorated by a threshold comparison method based on the traffic volume of each path and the number of allocated time slots.

  For example, for each path, the calculation CPU calculates a value indicating the accuracy of time slot allocation based on the traffic amount and the number of allocated time slots. If the calculated value is less than the threshold, the time slot allocation for that path is calculated. Detects that the accuracy of is worse.

  Further, for example, the value indicating the accuracy of time slot allocation may be a value obtained by converting the traffic amount required by the path into the required number of time slots and dividing the required time slot number by the allocated time slot number. However, it is not limited to this.

  When the calculation CPU detects that there is a path whose accuracy of time slot allocation has deteriorated during the calculation of the Rip-up & Re-allocate process, the calculation CPU performs the rearrange process of the time slot.

  As described above, in the present embodiment, the scheduler 40 performs the rearrange processing of the time slot when there is a path whose accuracy of time slot allocation has deteriorated during the calculation of the Rip-up & Re-allocate processing.

Therefore, it is possible to avoid deterioration in the accuracy of time slot allocation for each path, so that in the TDM network system having the same equipment amount, it is possible to increase the amount of traffic transferred with the same equipment amount. It is done.
(13) Thirteenth Embodiment This embodiment is a method for performing correction by rearrange processing in the middle of calculation described in the tenth embodiment, and is shown in Table 6 [3]. It corresponds to.

  FIG. 27 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 27, in the TDM network system of this embodiment, the scheduler 40 is different from the configuration of the first embodiment shown in FIG. 3 in that a memory monitoring device 424 is added. .

  The memory monitoring device 424 monitors the schedule table obtained by the Rip-up & Re-allocate process while calculating the Rip-up & Re-allocate process.

  The memory monitoring device 424 detects that the schedule table is in a missing state by the method based on threshold comparison described with reference to FIG.

  When the memory monitoring device 424 detects that the schedule table is in a missing state during the calculation of the Rip-up & Re-allocate processing, the memory monitoring device 424 notifies the arithmetic device 402 of a trigger for performing the rearrange processing of the time slot.

  As described above, in the present embodiment, the scheduler 40 performs the rearrange processing of the time slot when the schedule table is in a missing state during the calculation of the Rip-up & Re-allocate processing.

Therefore, since it is possible to avoid the schedule table being in a missing state, it is possible to increase the amount of traffic transferred with the same equipment amount in the TDM network system having the same equipment amount.
(14) Fourteenth Embodiment This embodiment is a method for performing correction by rearrange processing in the middle of calculation described in the tenth embodiment, and is shown in Table 6 [4]. It corresponds to.

  The configuration of this embodiment is the same as that of the thirteenth embodiment, but the monitoring target and detection target of the scheduler 40 are different.

  That is, the memory monitoring device 424 is assigned to each path on the traffic table requested by each path and the schedule table obtained by the Rip-up & Re-allocate process while calculating the Rip-up & Re-allocate process. Monitor the number of assigned time slots.

  The memory monitoring device 424 detects that there is a path whose time slot allocation accuracy has deteriorated by a method based on threshold comparison based on the traffic amount of each path and the number of allocated time slots. As a method for detecting deterioration in accuracy, the one exemplified in the twelfth embodiment can be used.

  When the memory monitoring device 424 detects that there is a path whose accuracy of time slot allocation has deteriorated during the calculation of the Rip-up & Re-allocate processing, the memory monitoring device 424 sends a trigger for performing the rearrange processing of the time slot to the arithmetic device 402. Notice.

  As described above, in the present embodiment, the scheduler 40 performs the rearrange processing of the time slot when there is a path whose accuracy of time slot allocation has deteriorated during the calculation of the Rip-up & Re-allocate processing.

Therefore, it is possible to avoid deterioration in the accuracy of time slot allocation for each path, so that in the TDM network system having the same equipment amount, it is possible to increase the amount of traffic transferred with the same equipment amount. It is done.
(15) Fifteenth Embodiment This embodiment is a method for performing correction by rearrange processing upon receiving a trigger notification described in the tenth embodiment, and is shown in Table 7 [ 5].

  FIG. 28 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 28, in the TDM network system of the present embodiment, the scheduler 40 adds a memory monitoring device 424 and an excess counter 425 as compared with the configuration of the first embodiment shown in FIG. Is different.

  The memory monitoring device 424 monitors the schedule table obtained by the Rip-up & Re-allocate process, and detects that the schedule table is in a missing state by the method based on threshold comparison described with reference to FIG.

  The memory monitoring device 424 periodically notifies the excess counter 425 whether or not the schedule table is in a missing tooth state.

  The excess counter 425 counts the cumulative number of times that the schedule table has become missing, and when the cumulative number reaches a threshold, notifies the arithmetic device 402 of a trigger for performing rearrange processing of the time slot.

  Alternatively, the excess counter 425 counts the number of consecutive times when the situation where the schedule table is in a missing state continues, and performs the rearrange processing of the time slot when the number of consecutive times reaches a threshold value. The trigger is notified to the computing device 402.

  As described above, in the present embodiment, the scheduler 40 performs rearrangement processing of time slots according to the number of times the schedule table is in a missing state.

Therefore, since it is possible to avoid the schedule table being in a missing state, it is possible to increase the amount of traffic transferred with the same equipment amount in the TDM network system having the same equipment amount.
(16) Sixteenth Embodiment This embodiment is a method for performing correction by rearrange processing upon receiving a trigger notification described in the tenth embodiment, and is shown in Table 7 [ 6].

  The configuration of this embodiment is the same as that of the fifteenth embodiment, but the monitoring target and detection target of the scheduler 40 are different.

  That is, the memory monitoring device 424 monitors the traffic amount requested by each path and the number of assigned time slots allocated to each path on the schedule table obtained by the Rip-up & Re-allocate process. Based on the traffic volume and the number of allocated time slots, it is detected that there is a path whose accuracy of time slot allocation has deteriorated by a threshold comparison method. As a method for detecting deterioration in accuracy, the one exemplified in the twelfth embodiment can be used.

  The memory monitoring device 424 periodically notifies the excess counter 425 whether there is a path whose accuracy of time slot allocation has deteriorated.

  The excess counter 425 counts the cumulative number of times that there is a path whose accuracy of time slot allocation has deteriorated, and when the cumulative number reaches the threshold, notifies the arithmetic unit 402 of a trigger for performing the rearrange processing of the time slot.

  Alternatively, the excess counter 425 counts the number of consecutive times when there is a continuous path where the accuracy of time slot allocation has deteriorated, and when the number of consecutive times reaches the threshold, A trigger for performing the arrangement process is notified to the arithmetic unit 402.

  As described above, in the present embodiment, the scheduler 40 performs rearrangement processing of time slots according to the number of times that the accuracy of time slot allocation to paths has deteriorated.

Therefore, it is possible to avoid deterioration in the accuracy of time slot allocation for each path, so that in the TDM network system having the same equipment amount, it is possible to increase the amount of traffic transferred with the same equipment amount. It is done.
(17) Seventeenth Embodiment This embodiment is the method described in the tenth embodiment, and (3) a method of applying correction by rearrangement processing upon receiving a trigger notification, and is shown in Table 7 [ 7].

  FIG. 29 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 29, in the TDM network system of this embodiment, the node 10 has the same components as the configuration of the first embodiment shown in FIG. The difference is that a threshold excess notification process is added.

  The controller 101 manages the queue length of each path whose source is the own node 10.

  The controller 101 periodically compares the queue length of each path with the node 10 as a transmission source with a threshold, and if there is a path that exceeds the threshold, transmits a threshold excess notification to the scheduler 40.

  When the arithmetic unit 402 of the scheduler 40 receives a threshold excess notification from any one of the nodes 10, it performs the rearrange processing of the time slot.

  As described above, in this embodiment, when the scheduler 40 receives a threshold excess notification from any one of the nodes 10, the scheduler 40 performs rearrange processing of time slots.

Therefore, since it is possible to avoid an unnecessarily long path queue length and an increase in delay, in a TDM network system having the same equipment amount, the amount of traffic transferred with the same equipment amount is increased and latency (delay) is increased. The effect that it can suppress is acquired.
(18) Eighteenth Embodiment This embodiment is a method for performing correction by rearrange processing upon receiving a trigger notification described in the tenth embodiment, and is shown in Table 7 [ 8].

  The configuration of this embodiment is the same as that of the seventeenth embodiment, but the monitoring target and detection target of each node 10 are different.

  That is, the controller 101 manages the tail drop rate of each path whose source is the node 10 itself. Tail drop is to discard packets that arrive at that time when the queue is full, and the tail drop rate is the rate at which packets arrived because the queue is full.

  The controller 101 periodically compares the tail drop rate of each path with the node 10 as a transmission source with a threshold, and if there is a path that exceeds the threshold, transmits a threshold excess notification to the scheduler 40.

  When the arithmetic unit 402 of the scheduler 40 receives a threshold excess notification from any one of the nodes 10, it performs the rearrange processing of the time slot.

  As described above, in this embodiment, when the scheduler 40 receives a threshold excess notification from any one of the nodes 10, the scheduler 40 performs rearrange processing of time slots.

Therefore, since it is possible to avoid an increase in the number of paths discarded at the node 10, in the TDM network system having the same equipment amount, an effect that the traffic amount transferred with the same equipment amount can be increased. It is done.
(19) Nineteenth Embodiment This embodiment is the method described in the tenth embodiment, and (3) a method of applying correction by rearrangement processing upon receiving a trigger notification, and is shown in Table 7 [ 9].

  FIG. 30 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 30, in the TDM network system of the present embodiment, the node 10 is added with an allocation accuracy monitoring device 107 as compared with the configuration of the first embodiment shown in FIG. Different.

  The controller 101 manages the amount of traffic requested by each path whose source is the own node 10 and the number of assigned time slots allocated to each path by the scheduler 40.

  The allocation accuracy monitoring apparatus 107 detects that there is a path whose time slot allocation accuracy has deteriorated, using a threshold comparison method, based on the traffic amount of each path and the number of allocated time slots. As a method for detecting deterioration in accuracy, the one exemplified in the twelfth embodiment can be used.

  If there is a path whose time slot allocation accuracy has deteriorated, the controller 101 transmits an optimal solution deviation notification to the scheduler 40.

  When the computing device 402 of the scheduler 40 receives an optimal solution divergence notification from any one of the nodes 10, it performs the rearrange processing of the time slot.

  As described above, in this embodiment, when the scheduler 40 receives an optimal solution deviation notification from any one of the nodes 10, the scheduler 40 performs a rearrange process of time slots.

Therefore, it is possible to avoid deterioration in the accuracy of time slot allocation for each path, so that in the TDM network system having the same equipment amount, it is possible to increase the amount of traffic transferred with the same equipment amount. It is done.
(20) 20th Embodiment In the 10th embodiment, rearrange processing is performed using the remainder of the time slot allocation calculation time, and the time slot allocation calculation is aborted by the abort timer 423. .

  On the other hand, in the present embodiment, in addition to the time slot allocation calculation abortion by the abort timer 423, the accuracy of the schedule table missing state and time slot assignment deteriorates within a certain time until the abortion of the abort timer 423. Even if the improvement is made, the calculation is terminated.

  FIG. 31 shows an example of the configuration of the TDM network system of this embodiment.

  As shown in FIG. 31, in the TDM network system of this embodiment, the scheduler 40 is different from the configuration of the tenth embodiment shown in FIG. 25 in that a memory monitoring device 424 is added. .

  After the Rip-up & Re-allocate process, the arithmetic unit 402 performs the time slot process using the remainder of the time slot allocation calculation time.

  The abort timer 423 periodically notifies the arithmetic unit 402 of a calculation abort trigger for time slot allocation.

  The memory monitoring device 424 monitors whether the schedule table tooth missing state and time slot allocation accuracy deterioration have been improved. If the schedule table tooth missing state and time slot allocation accuracy deterioration have improved, A calculation abort trigger is notified to the computing device 402.

  Therefore, after the Rip-up & Re-allocate process, the arithmetic unit 402 uses the remainder of the time slot allocation calculation time, and performs the time slot process until an abort notification is received from the abort timer 423 or the memory monitoring device 424. become.

As described above, in the present embodiment, the scheduler 40 aborts the calculation of the time slot allocation even when the tooth missing state of the schedule table or the accuracy deterioration of the time slot allocation is improved. Therefore, even if before the time-out of the abort timer 423, if the missing tooth state or accuracy deterioration is improved, the computation can be aborted, so that the effect of further shortening the time slot allocation calculation time can be obtained.
(21) Twenty-first Embodiment In the seventeenth to nineteenth embodiments, when the scheduler 40 receives a threshold excess notification or an optimal solution divergence notification from any one of the nodes 10, it performs the rearrange processing of the time slot. It was.

  On the other hand, in the present embodiment, when the number of times the threshold value excess notification or the optimum solution deviation notification is received within a certain time reaches the threshold value, the time slot rearrange processing is performed.

  FIG. 32 shows an example of the configuration of the TDM network system of this embodiment. FIG. 32 is based on the nineteenth embodiment shown in FIG. 30, and each node 10 performs the optimal solution deviation notification process.

  As shown in FIG. 32, in the TDM network system of the present embodiment, the scheduler 40 adds an optimal solution deviation notification counter 426 and a timer 427, compared to the configuration of the nineteenth embodiment shown in FIG. Is different.

  The optimum solution divergence notification counter 426 counts the number of times the optimum solution divergence notification is received from the node 10 within a predetermined time, and when the counter value reaches a threshold value, the arithmetic device 402 is triggered by the rearrange processing of the time slot. Notice.

  The timer 427 periodically notifies the optimal solution deviation notification counter 426 of the trigger.

  Therefore, the optimal solution deviation notification counter 426 counts the number of receptions of the optimal solution deviation notification while receiving the notification of the next trigger from the timer 427.

  As described above, in the present embodiment, the scheduler 40 performs the rearrange processing of the time slot when the number of times the optimal solution deviation notification is received from the node 10 reaches the threshold value.

  Therefore, it is possible to avoid deterioration in the accuracy of time slot allocation for each path, so that in the TDM network system having the same equipment amount, it is possible to increase the amount of traffic transferred with the same equipment amount. It is done.

  Also, even if the accuracy of time slot allocation for a certain path deteriorates, the accuracy may improve within a certain time, and as a result, the rearrange processing when the number of received optimal solution deviation notifications does not reach the threshold The effect that it can be avoided is obtained.

In this embodiment, the seventeenth and eighteenth embodiments shown in FIG. 29 can be used as a base. In this case, the number of received threshold excess notifications is used instead of the optimum solution deviation notification counter 426. A threshold excess notification counter for counting may be provided.
(22) Twenty-second embodiment In the seventeenth to nineteenth embodiments, when the scheduler 40 receives a threshold excess notification or an optimal solution divergence notification from any one of the nodes 10, it performs the rearrange processing of the time slot. It was.

  On the other hand, in the present embodiment, for each path, the number of times the threshold excess notification or the optimal solution deviation notification is received within a certain time is counted, and the path whose number has reached the threshold is prioritized and Rip-up & Re -Time slot allocation is performed in the allocate process.

  FIG. 33 shows an example of the configuration of the TDM network system of this embodiment. FIG. 33 is based on the nineteenth embodiment shown in FIG. 30, and each node 10 performs an optimal solution deviation notification process.

  As shown in FIG. 33, in the TDM network system of the present embodiment, the scheduler 40 and the node 10 have the same constituent elements as compared with the configuration of the twenty-second embodiment shown in FIG. The operation is different.

  That is, when there is a path whose time slot allocation accuracy has deteriorated, the controller 101 of the node 10 transmits an optimal solution deviation notification including the identifier of the path to the scheduler 40.

  The optimal solution divergence notification counter 426 counts the number of receptions of the optimal solution divergence notification from the node 10 within a predetermined time for each path, and when there is a path whose counter value reaches the threshold value, the path is sent to the arithmetic unit 402. Notice.

  The timer 427 periodically notifies the optimal solution deviation notification counter 426 of the trigger.

  Therefore, the optimal solution deviation notification counter 426 counts the number of receptions of the optimal solution deviation notification while receiving the notification of the next trigger from the timer 427.

  The computing device 402 performs time slot allocation in the Rip-up & Re-allocate process with priority given to the path notified from the optimal solution deviation notification counter 426.

  As described above, in the present embodiment, when there is a path in which the number of times the optimal solution divergence notification has been received from the node 10 has reached the threshold, the scheduler 40 gives priority to the path and performs time in the Rip-up & Re-allocate processing. Slot allocation is performed.

  Accordingly, since the time slot allocation can be performed in the Rip-up & Re-allocate process with priority given to the path whose accuracy of time slot allocation has deteriorated, the traffic transferred with the same equipment amount in the TDM network system having the same equipment amount. The effect that the amount can be increased is obtained.

  In this embodiment, the seventeenth and eighteenth embodiments shown in FIG. 29 can be used as a base. In this case, the number of received threshold excess notifications is used instead of the optimum solution deviation notification counter 426. A threshold excess notification counter for counting may be provided.

  In the present embodiment, the trigger for performing the rearrange processing and the trigger for aborting the calculation of the rearrange processing (time slot allocation) are arbitrary, and can be combined with any of the tenth to twenty-first embodiments described above. Is possible.

  As described above, in the tenth to twenty-second embodiments, examples of the method of combining the rearrange processing of the time slot with the Rip-up & Re-allocate method have been described, but the concept of this method will be supplemented.

  In the method of combining the Rip-up & Re-allocate method with the rearrange processing of the time slot, the time slot operation (cut / paste / move) is performed on the schedule table during the time slot assignment.

  However, when the time slot operation is performed, it is considered that the policy differs depending on the application.

  For example, in a concentrated network, the number of paths is large, and the required TS per path is small. From this, it is considered effective to give priority to increasing the adjacent time slots in the link direction on the schedule table.

  On the other hand, since a large number of users are multiplexed on one path in the core network, the number of paths is small and the required bandwidth per path is large. From this, it is considered effective to give priority to increasing the adjacent time slots in the time direction on the schedule table (the optical overhead can be reduced between the adjacent time slots).

  FIG. 34 shows an example of a method of increasing adjacent time slots in the link direction and a method of increasing adjacent time slots in the time direction.

  As shown in FIG. 34, increasing adjacent time slots in the link direction means assigning time slots so as to be continuous in the horizontal direction in FIG. In the example of FIG. 34, when the allocated time slot assigned to the path from node C to node A is moved, it is moved to time slot position 4.

  If there is no space in the horizontal direction and the time slots are clogged, the time slot allocation efficiency increases, so that more users can be accommodated in the same equipment.

  On the other hand, increasing adjacent time slots in the time direction means assigning time slots so as to be continuous in the vertical direction in FIG. In the example of FIG. 34, a time slot is allocated by dividing the path from node A to node D. Therefore, continuous time slot allocation can be realized by moving the allocated time slot to the time slot position 5.

  If time slots are continuously assigned to the same path in the vertical direction, an operation in which the optical overhead between the time slots is deleted becomes possible. It is also suitable for accommodating large-capacity communications.

  The present invention has been described above with reference to the embodiments, but the present invention is not limited to the above embodiments. Various modifications that can be understood by those skilled in the art can be made to the configuration and details of the present invention without departing from the gist of the present invention.

  For example, in the first to twenty-second embodiments, an example in which the scheduler 40 of the present invention is configured using an electronic circuit has been shown, but part or all of the scheduler 40 may be realized by software on a computer.

  In the first to twenty-second embodiments, some triggers for performing rearrange processing and triggers for canceling the calculation of rearrange processing (time slot allocation) have been described. However, these are applied to other embodiments. It may also be applied in combination of two or more.

  The method performed by the scheduler 40 of the present invention may be applied to a program for causing a computer to execute. In addition, the program can be stored in a storage medium and can be provided to the outside via a network.

10 nodes 101 controller 102 switch 103 transmitter (Tx)
104 Receiver (Rx)
105 Buffer 106 IO Unit 107 Allocation Accuracy Monitoring Device 20 Link 30 Host Computer 40 Scheduler 401 IO Unit 402 Arithmetic Device 403 Memory 404 Traffic Information Holding Unit 405 Node Grouper 406 In-Group Schedule Calculation Unit 407 In-Group Schedule Table Holding Unit 408, 408-1 , 408-2 Inter-group schedule calculation unit 409, 409-1, 409-2 Inter-group schedule table holding unit 410, 410-1, 410-2 Virtual schedule table calculation unit 411 abort timer 412 calculation abort notification unit 413, 413 1,413-2 TS rearrangement allocation calculation unit 414, 414-1, 414-2 actual schedule table calculation unit 415, 415-1, 415-2 actual schedule table storage Unit 416 Node control signal generation unit 417 Abort instruction detection unit 418 Virtual schedule table monitor unit 419 Allocated path monitoring unit 420 Control signal counter 421 Group traffic information holding unit 422 Group route information holding unit 423 Abort timer 424 Memory monitoring device 425 Excess counter 426 Optimal solution deviation notification counter

Claims (6)

In a TDM network system comprising a plurality of nodes, a link connecting the nodes, and a scheduler that assigns a time slot to each path connecting a source node and a destination node. ,
The scheduler
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. A computing device that allocates time slots and creates a schedule table that indicates the allocation status of the time slots for each path;
A memory for storing the schedule table,
The arithmetic unit is:
Until the calculation abort trigger is received, the allocated time slot on the schedule table is rearranged to an empty time slot position ,
The calculation abort trigger is
(1) When the schedule length of the schedule table is equal to or shorter than the TDM frame length,
(2) A path assigned to a time slot position exceeding the TDM frame length on the schedule table is stored in a list format, and a path whose assigned position is changed within the TDM frame length range by relocation is excluded from the list. And if the list is empty,
(3) Count the number of received signals for reporting traffic volume from the plurality of nodes, and when the counter value reaches a threshold value,
(4) Every time a certain time elapses,
(5) Due to rearrangement within a certain time, the value indicating the clogging status of the allocated time slot on the schedule table is equal to or greater than a threshold value, and the time slot calculated based on the traffic volume and the number of allocated time slots If there are no more paths whose allocation accuracy is less than the threshold,
A TDM network system, which is notified at any one of the timings . In a TDM network system comprising a plurality of nodes, a link connecting the nodes, and a scheduler that assigns a time slot to each path connecting a source node and a destination node. ,
The scheduler
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. A computing device that allocates time slots and creates a schedule table that indicates the allocation status of the time slots for each path;
A memory for storing the schedule table,
The arithmetic unit is:
When the condition is satisfied, the allocated time slot on the schedule table is rearranged to an empty time slot position ,
If the above conditions are met,
(1) When there is a path whose value representing the allocation accuracy of the time slot calculated based on the traffic amount and the number of allocated time slots is less than the threshold,
(2) Counting the cumulative number of times that the value indicating the clogged status of the assigned time slot on the schedule table is less than the threshold value, or the status of (1), and the counter value has reached the threshold value If
(3) When a notification that the queue length of the path exceeds the threshold is received from any of the plurality of nodes,
(4) When a notification that the tail drop rate of the path exceeds the threshold is received from any of the plurality of nodes,
Any one of the TDM network systems, In a TDM network system comprising a plurality of nodes, a link connecting the nodes, and a scheduler that assigns a time slot to each path connecting a source node and a destination node. ,
The scheduler
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. A computing device that allocates time slots and creates a schedule table that indicates the allocation status of the time slots for each path;
A memory for storing the schedule table,
The arithmetic unit is:
When receiving a notice to perform rearrangement of time slots, rearrange allocated time slots on the schedule table to empty time slot positions ;
The notification is
(1) An optimal solution deviation notification indicating that there is a path whose accuracy of time slot allocation has deteriorated by any one of the nodes,
(2) A threshold excess notification indicating that there is a path by which the tail drop rate of each path exceeds a predetermined threshold by any one of the nodes;
(3) a notification indicating that the number of times the optimal solution deviation notification has been received from the node within a predetermined time has reached a threshold;
(4) a notification indicating that the number of times the threshold excess notification has been received from the node within a certain time has reached a threshold;
Any one of the TDM network systems, The arithmetic unit is:
When creating the schedule table,
Grouping the plurality of nodes;
Scheduling within the group,
Schedule between groups,
The TDM network system according to any one of claims 1 to 3 , wherein the schedule table is created by substituting a scheduling result in a group into a scheduling result between groups. The arithmetic unit is:
When creating the schedule table,
For each path, calculate the difference in traffic volume between the previous scheduling execution and the current scheduling execution,
In response to the decrease in the traffic volume of the path, a stripping process is performed to delete the assigned time slot assigned to the path from the schedule table created during the previous scheduling execution,
Depending on the traffic volume of the path is increased, and paste processing of adding the time slots to the path in the schedule table created in the previous scheduling execution, according to any one of claims 1 3 TDM network system. In a TDM network system, comprising: a plurality of nodes; a link that connects the nodes; and a scheduler that assigns a time slot to each path connecting the source node and the destination node. In the scheduling method,
The traffic volume in the path is counted from the plurality of nodes, and for each path, the number of time slots required for the path is calculated based on the traffic volume in the path, and the path is calculated based on the calculated time slot number. Assign a time slot and create a schedule table that shows the time slot assignment status for each path.
Storing the schedule table in a memory;
Until the calculation abort trigger is received, the allocated time slot on the schedule table is rearranged to an empty time slot position ,
The calculation abort trigger is
(1) When the schedule length of the schedule table is equal to or shorter than the TDM frame length,
(2) A path assigned to a time slot position exceeding the TDM frame length on the schedule table is stored in a list format, and a path whose assigned position is changed within the TDM frame length range by relocation is excluded from the list. And if the list is empty,
(3) Count the number of received signals for reporting traffic volume from the plurality of nodes, and when the counter value reaches a threshold value,
(4) Every time a certain time elapses,
(5) Due to rearrangement within a certain time, the value indicating the clogging status of the allocated time slot on the schedule table is equal to or greater than a threshold value, and the time slot calculated based on the traffic volume and the number of allocated time slots If there are no more paths whose allocation accuracy is less than the threshold,
A scheduling method characterized in that notification is made at any one of the timings .

Images