Communication management list generation device, communication management list generation method, and storage medium in which communication management list generation program is stored

Abstract

A communication management list generation device 20 generates a communication management list composed of communication management information including time of day information corresponding to a prescribed time of day and communication information indicating a communication process started at a prescribed time of day and not using the same path at the same time. The communication management list generation device is provided with: a determination means 21 for determining, regarding whether information on the communication process can be added to the communication information, each communication management information in descending order of time (early time first) corresponding to the time of day information; and an addition means 22 for adding information on the communication process to the communication information of the communication management information determined at a stage at which it was determined by the determination means 21 that addition is possible.

Claims

1. A communication management list generation device comprising: a generation unit for generating a communication management list constituted by communication management information including time information associated with a predetermined time, and communication information indicating communication processing which is started at the predetermined time and which does not use a same route simultaneously; a determination unit for determining each piece of communication management information in an ascending order of time associated with the time information regarding whether or not communication processing information is addable to communication information; and an addition unit for adding the communication processing information to communication information of communication management information which is determined to be addable at a time of determination by the determination unit, wherein the communication processing information comprises shortest route information, and wherein data is transmitted over a shortest route selected based on the communication processing information.

2. The communication management list generation device according to claim 1, wherein the determination unit determines whether or not communication processing information is addable in a descending order of sum of distances between a shortest route to be used with respect to a plurality of communication processings, and a shortest route to be used by other communication processings.

3. The communication management list generation device according to claim 1, further comprising a measuring unit for measuring a time required for overall communication processing to be performed by using a communication management list generated by adding all pieces of communication processing information as an addition target, wherein the measuring unit outputs a communication management list having the shortest required time among all patterns on a communication management list to be generated based on communication processing information as the addition target.

4. The communication management list generation device according to claim 1, wherein the communication processing information is shortest route information in which a sum of distances to a shortest route to be used by other communication processing is maximum among all patterns on a shortest route to be used by the communication processing.

5. A communication management list generation method comprising: generating a communication management list constituted by communication management information including time information associated with a predetermined time, and communication information indicating communication processing which is started at the predetermined time and which does not use a same route simultaneously; determining each piece of communication management information in an ascending order of time associated with the time information regarding whether or not communication processing information is addable to communication information; and adding the communication processing information to communication information of communication management information which is determined to be addable at a time of determination, wherein the communication processing information comprises shortest route information, and wherein data is transmitted over a shortest route selected based on the communication processing information.

6. The communication management list generation method according to claim 5, further comprising determining whether or not communication processing information is addable in a descending order of sum of distances between a shortest route to be used with respect to a plurality of communication processings, and a shortest route to be used by other communication processings.

7. The communication management list generation method according to claim 5, further comprising: measuring a time required for overall communication processing to be performed by using a communication management list generated by adding all pieces of communication processing information as an addition target; and outputting a communication management list having the shortest required time among all patterns on a communication management list to be generated based on communication processing information as the addition target.

8. A non-transitory storage medium storing the communication management list generation program causing a computer to execute: generation processing of generating a communication management list constituted by communication management information including time information associated with a predetermined time, and communication information indicating communication processing which is started at the predetermined time and which does not use a same route simultaneously; determination processing of determining each piece of communication management information in an ascending order of time associated with the time information regarding whether or not communication processing information is addable to the communication information; and addition processing of adding the communication processing information to communication information of communication management information which is determined to be addable at a time of determination in the determination processing, wherein the communication processing information comprises shortest route information, and wherein data is transmitted over a shortest route selected based on the communication processing information.

9. The non-transitory storage medium storing the communication management list generation program according to claim 8, the communication management list generation program causing the computer to further execute determination processing of determining whether or not communication processing information is addable in a descending order of sum of distances between a shortest route to be used with respect to a plurality of communication processings, and a shortest route to be used by other communication processings.

10. The non-transitory storage medium storing the communication management list generation program according to claim 8, the communication management list generation program causing the computer to further execute: measuring processing of measuring a time required for overall communication processing to be performed by using a communication management list generated by adding all pieces of communication processing information as an addition target; and output processing of outputting a communication management list having the shortest required time among all patterns on a communication management list to be generated based on communication processing information as the addition target.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a block diagram illustrating a configuration example of a first example embodiment of a timeslot list generation device 100 according to the present invention.

(2) FIG. 2 is a flowchart illustrating an operation of generation processing by the timeslot list generation device 100 in the first example embodiment.

(3) FIG. 3 is a flowchart illustrating an operation of route list generation processing by a shortest sparse route generation means 110.

(4) FIG. 4 is an explanatory diagram illustrating an example of a set of routes, in which pairs of start points and finish points are identical.

(5) FIG. 5 is a flowchart illustrating an operation of timeslot list generation processing by a timeslot allocation means 120.

(6) FIG. 6 is a block diagram illustrating a configuration example of a second example embodiment of a timeslot list generation device 100 according to the present invention.

(7) FIG. 7 is a flowchart illustrating an operation of generation processing by the timeslot list generation device 100 in the second example embodiment.

(8) FIG. 8 is a block diagram illustrating a configuration example of a third example embodiment of a timeslot list generation device 100 according to the present invention.

(9) FIG. 9 is a flowchart illustrating an operation of generation processing by the timeslot list generation device 100 in the third example embodiment.

(10) FIG. 10 is a flowchart illustrating an operation of timeslot list generation processing by a comprehensive timeslot allocation means 140.

(11) FIG. 11 is an explanatory diagram illustrating an example of a network topology in a range where communication as a processing target in a fourth example embodiment is performed.

(12) FIG. 12 is an explanatory diagram illustrating an example of an endpoint pair list to be input to a shortest sparse route generation means 110 in the fourth example embodiment.

(13) FIG. 13 is an explanatory diagram illustrating an example of a route list to be generated by the shortest sparse route generation means 110 in the fourth example embodiment.

(14) FIG. 14 is an explanatory diagram illustrating an example of a timeslot list to be generated by a timeslot allocation means 120 in the fourth example embodiment.

(15) FIG. 15 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 14.

(16) FIG. 16 is an explanatory diagram illustrating an example of a rearranged route list to be generated by a descending order distance route rearranging means 130 in the fourth example embodiment.

(17) FIG. 17 is an explanatory diagram illustrating another example of a timeslot list to be generated by the timeslot allocation means 120 in the fourth example embodiment.

(18) FIG. 18 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 17.

(19) FIG. 19 is an explanatory diagram illustrating an example of a timeslot list to be generated by a comprehensive timeslot allocation means 140 in the fourth example embodiment.

(20) FIG. 20 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 19.

(21) FIG. 21 is a block diagram illustrating an outline of the communication management list generation device according to the present invention.

(22) FIG. 22 is an explanatory diagram illustrating an example of communication processing to be performed by using wormhole routing.

(23) FIG. 23 is an explanatory diagram illustrating an example of a timeslot list.

(24) FIG. 24 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 23.

(25) FIG. 25 is a block diagram illustrating a configuration example of a timeslot list generation device described in NPL 1.

(26) FIG. 26 is an explanatory diagram illustrating another example of a timeslot list.

(27) FIG. 27 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 26.

EXAMPLE EMBODIMENT

First Example Embodiment

(28) [Description on Configuration]

(29) In the following, an example embodiment of the present invention is described with reference to the drawings. FIG. 1 is a block diagram illustrating a configuration example of a first example embodiment of a timeslot list generation device 100 according to the present invention. The timeslot list generation device 100 is, for example, a timeslot list generation device for generating a timeslot list to be used when communication using wormhole routing is performed in such a manner that blocking does not occur in communication.

(30) The timeslot list generation device 100 illustrated in FIG. 1 includes a shortest sparse route generation means 110 and a timeslot allocation means 120.

(31) As illustrated in FIG. 1, the shortest sparse route generation means 110 receives network topology information and an endpoint pair list as an input. The shortest sparse route generation means 110 calculates a shortest route, within a communication network, connecting a start point and a finish point indicated by endpoint pair information constituting an endpoint pair list for each piece of endpoint pair information.

(32) Then, the shortest sparse route generation means 110 generates a route list constituted by the calculated shortest routes. Routes included in the route list do not pass through a same link within a communication network during a same time zone as much as possible.

(33) The timeslot allocation means 120 allocates, by using the route list as an input, a route to each piece of communication management information having a different timeslot in such a manner that routes included in a route list do not overlap each other. Note that an expression that routes do not overlap each other means that the respective routes do not pass through a same link within a communication network during a same time zone. The timeslot allocation means 120 outputs a timeslot list, in which routes within an allocatable route list are all allocated.

(34) [Description on Operation]

(35) In the following, an operation of the timeslot list generation device 100 in the present example embodiment is described with reference to FIG. 2. FIG. 2 is a flowchart illustrating an operation of generation processing by the timeslot list generation device 100 in the first example embodiment.

(36) The shortest sparse route generation means 110 receives an endpoint pair list and network topology information as an input. Then, the shortest sparse route generation means 110 generates a route list constituted by shortest routes associated with respective pieces of endpoint pair information (Step S110).

(37) Then, the timeslot allocation means 120 allocates routes within the route list to communication management information in such a manner that the routes do not pass through a same link during a same time zone (Step S120). The timeslot allocation means 120 outputs a timeslot list, in which allocatable routes within the route list are all allocated. After outputting the timeslot list, the timeslot list generation device 100 terminates the generation processing.

(38) In the following, an operation of the shortest sparse route generation means 110 in the present example embodiment is described with reference to FIG. 3. FIG. 3 is a flowchart illustrating an operation of route list generation processing by the shortest sparse route generation means 110. Specifically, processing of Step S111 to Step S118 illustrated in FIG. 3 corresponds to processing of Step S110 illustrated in FIG. 2.

(39) The shortest sparse route generation means 110 receives an endpoint pair list and network topology information as an input. Specifically, the shortest sparse route generation means 110 enters a calculation loop (Step S111).

(40) Then, the shortest sparse route generation means 110 calculates a shortest route from a start point to a finish point indicated by endpoint pair information within the input endpoint pair list. Note that a shortest route may be calculated by a well-known method, for example, and a plurality of shortest routes may be calculated. The shortest sparse route generation means 110 adds the calculated shortest route in a shortest route list stored in a working area (Step S112).

(41) The shortest sparse route generation means 110 repeats processing of Step S112 during a period when a start point of endpoint pair information for which a shortest route is not calculated within the input endpoint pair list is present. When shortest routes from all start points of endpoint pair information within the endpoint pair list are calculated, the shortest sparse route generation means 110 exits from the calculation loop (Step S113).

(42) Then, the shortest sparse route generation means 110 receives an endpoint pair list and a shortest route list as an input. Specifically, the shortest sparse route generation means 110 enters an addition loop (Step S114).

(43) The shortest sparse route generation means 110 searches a set of routes, in which pairs of start points and finish points are identical, from routes within the input shortest route list (Step S115).

(44) FIG. 4 is an explanatory diagram illustrating an example of a set of routes, in which pairs of start points and finish points are identical. In an example illustrated in FIG. 4, start points of arbitrary routes included in a set are all n1, and finish points of the arbitrary routes are all n2.

(45) Then, the shortest sparse route generation means 110 acquires a route, in which a sum of distances to other routes within the shortest route list is largest, from the set of routes acquired in Step S115, and sets the acquired route as a sparse route (Step S116). A distance d(p1, p2) between a route p1 and a route p2 is defined as expressed by the following Eq. (1).
d(p1,p2)::=max(|p1|,|p2|)overlap(p1,p2)Eq. (1)

(46) In Eq. (1), p denotes a route, and |p| denotes the number of nodes through which the route p passes, specifically, a route length. Further, max(|p1|, |p2|) in Eq. (1) denotes a longer route length between the route length of |p1| and the route length of |p2|. Further, overlap(p1, p2) in Eq. (1) denotes the number of links through which p1 and p2 pass from a start point in a same distance, and is defined as expressed by the following Eq. (2).
overlap(p1,p2)::=|{p1[i]=p2[i]|0<=i<min(|p1|,|p2|)}| Eq. (2)

(47) In Eq. (2), p[i] denotes a node through which the route p passes in the i-th order. p[0] denotes a start node, and p[|p|1] denotes a finish node. Further, in Eq. (2), min(|p1|, |p2|) denotes a shorter route length between the route length of |p1| and the route length of |p2|.

(48) For example, a case is considered in which the route p1 and the route p2 are defined as follows.
p1::=n1.fwdarw.n2.fwdarw.n3.fwdarw.n5.fwdarw.n6
p2::=n1.fwdarw.n2.fwdarw.n4.fwdarw.n3.fwdarw.n5

(49) In the aforementioned case, the route p1 and the route p2 pass through the same link n1.fwdarw.n2 from a start point in a distance 0. Since no other common link to pass through is present, overlap(p1, p2)=2. Specifically, {p1[i]=p2[i]|0<=i<min(|p1|, |p2|)} indicates a set of common physical links through which the route p1 and the route p2 pass from a start point in a same distance i.

(50) A sum of distances between a route calculated in Step S116 and other routes within the shortest route list is a value indicated by d(p, p.sub.k), for example. The shortest sparse route generation means 110 acquires a route at which d(p, p.sub.k) becomes maximum, and adds the acquired route in the route list, as a sparse route (Step S117).

(51) The shortest sparse route generation means 110 repeats processing of Step S115 to Step S117 during a period when endpoint pair information for which a sparse route is not added within the input endpoint pair list is present. When sparse routes of all pieces of endpoint pair information within the endpoint pair list are added, the shortest sparse route generation means 110 exits from the addition loop (Step S118), and terminates the route list generation processing.

(52) Next, an operation of the timeslot allocation means 120 in the present example embodiment is described with reference to FIG. 5. FIG. 5 is a flowchart illustrating an operation of timeslot list generation processing by the timeslot allocation means 120. Specifically, processing of Step S121 to Step S131 illustrated in FIG. 5 corresponds to processing of Step S120 illustrated in FIG. 2.

(53) The timeslot allocation means 120 receives a route list generated by the shortest sparse route generation means 110 as an input. Specifically, the timeslot allocation means 120 enters a generation loop (Step S121).

(54) Then, the timeslot allocation means 120 sets a timeslot allocation time t to 0 (Step S122). The timeslot allocation time t is a value associated with a timeslot of communication management information. Then, the time slot allocation means 120 extracts one route from the input route list (Step S123). Specifically, the timeslot allocation means 120 enters an allocation loop (Step S124).

(55) The timeslot allocation means 120 determines whether or not a route extracted in Step S123 is allocatable to communication management information at the time t (Step S125). When the extracted route does not pass through a same link during a same time zone as a communication route of communication management information at the time t within the timeslot list, the timeslot allocation means 120 determines that the route is allocatable.

(56) When it is determined that the route is not allocatable (No in Step S126), the timeslot allocation means 120 adds 1 to the timeslot allocation time t (Step S127). Then, the timeslot allocation means 120 performs processing of Step S125 again.

(57) When it is determined that the route is allocatable (Yes in Step S126), the timeslot allocation means 120 allocates the route extracted in Step S123 to communication management information at the time t (Step S130). Then, the timeslot allocation means 120 performs processing of Step S122 again.

(58) The timeslot allocation means 120 repeats processing of Step S125 to Step S127 until the timeslot allocation time t reaches an upper limit. When the timeslot allocation time t reaches the upper limit, the timeslot allocation means 120 exits from the allocation loop (Step S128), and deletes the route extracted in Step S123 (Step S129).

(59) Note that the timeslot allocation means 120 may not delete a route extracted in Step S123, and may store the route in a working area. After deletion, the timeslot allocation means 120 performs processing of Step S122 again.

(60) The upper limit of the timeslot allocation time t is a constant to be given from a user of the timeslot list generation device 100, for example. The upper limit of the timeslot allocation time t is determined for each target communication network.

(61) The timeslot allocation means 120 repeats processing of Step S122 to Step S130 during a period when a route which is not processed within an input route list is present, specifically, until the input route list becomes empty. When all routes within the route list are processed, the timeslot allocation means 120 exits from the generation loop (Step S131), and terminates the timeslot list generation processing.

(62) [Description on Advantageous Effects]

(63) Next, advantageous effects of the present example embodiment are described. In the timeslot list generation device of the present example embodiment, the shortest sparse route generation means generates a route group in such a manner that a same link is not used for two or more pieces of communication during a same period as much as possible, and the timeslot allocation means allocates routes which do not pass through a same link simultaneously to same communication management information from the route group.

(64) When routes are allocated, the timeslot allocation means allocates the routes in an order from communication management information having a small timeslot so that the routes are allocated to communication management information having a less number of route groups as small as possible. Thus, the timeslot list generation device is able to generate a timeslot list with which communication is performed at a shorter time interval. By using the generated timeslot list, larger communication is performed within a shorter period.

(65) When a timeslot list generated by a method described in NPL 1 is used, since there is no time zone during which execution times overlap between pieces of communication of each segment, a large number of links which are not used in communication are present.

(66) The timeslot list generation device in the present example embodiment does not divide communication routes into segments. Further, the timeslot allocation means in the present example embodiment is also able to allocate each communication route to communication management information, in which a communication route within a timeslot list remains empty. Therefore, by using the timeslot list generated in the present example embodiment, a time zone during which execution times overlap between pieces of communication is present, and larger communication is performed within a shorter period.

Second Example Embodiment

(67) [Description on Configuration]

(68) Next, a second example embodiment of the present invention is described with reference to the drawings. FIG. 6 is a block diagram illustrating a configuration example of the second example embodiment of a timeslot list generation device 100 according to the present invention.

(69) The timeslot list generation device 100 illustrated in FIG. 6 includes a shortest sparse route generation means 110, a timeslot allocation means 120, and a descending order distance route rearranging means 130. Unlike the timeslot list generation device 100 illustrated in FIG. 1, the timeslot list generation device 100 in the present example embodiment includes the descending order distance route rearranging means 130.

(70) The descending order distance route rearranging means 130 receives a route list generated by the shortest sparse route generation means 110 as an input. The descending order distance route rearranging means 130 calculates a sum of distances between a route within the route list and other routes. Then, the descending order distance route rearranging means 130 rearranges the routes within the route list in the descending order of sum of distances, and generates a new route list, in which the routes are rearranged.

(71) By rearranging the routes within the route list by the descending order distance route rearranging means 130 in the descending order of sum of distances, the timeslot allocation means 120 is able to allocate routes to communication management information in an order from a route having a small amount of overlapping with other routes. Thus, it is easy to allocate routes having a small amount of overlapping with respect to other routes to same communication management information, and a possibility that a timeslot number of a timeslot list to be generated is reduced increases, as compared with the first example embodiment.

(72) [Description on Operation]

(73) In the following, an operation of the timeslot list generation device 100 in the present example embodiment is described with reference to FIG. 7. FIG. 7 is a flowchart illustrating an operation of generation processing by the timeslot list generation device 100 in the second example embodiment.

(74) The shortest sparse route generation means 110 receives an endpoint pair list and network topology information as an input. Then, the shortest sparse route generation means 110 generates a route being a shortest route connecting between endpoints, and which does not pass through a same link simultaneously with another route as much as possible for each piece of endpoint pair information within the endpoint pair list.

(75) Then, the shortest sparse route generation means 110 outputs a route list constituted by the generated routes (Step S210). Note that processing of Step S210 is the same as processing of Step S110 illustrated in FIG. 2.

(76) Then, the descending order distance route rearranging means 130 rearranges the routes within the route list output by the shortest sparse route generation means 110 in the descending order of sum of distances to other routes (Step S220). The descending order distance route rearranging means 130 outputs a route list, in which the routes are rearranged.

(77) Then, the timeslot allocation means 120 allocates routes within the route list output by the descending order distance route rearranging means 130 to communication management information in such a manner that the routes do not pass through a same link during a same time zone (Step S230). Since routes are rearranged in the descending order of sum of distances to other routes in the route list, the timeslot allocation means 120 is able to allocate the routes to communication management information in an order from a route having a small amount of overlapping with other routes. The timeslot allocation means 120 outputs a timeslot list, in which allocatable routes within the route list are all allocated.

(78) Note that processing of Step S230 is the same as processing of Step 120 illustrated in FIG. 2. After outputting a timeslot list, the timeslot list generation device 100 terminates the generation processing.

(79) [Description on Advantageous Effects]

(80) Next, advantageous effects of the present example embodiment are described. The descending order distance route rearranging means in the present example embodiment rearranges routes within a route list in the descending order of sum of distances to other routes. Therefore, the timeslot allocation means is able to allocate routes in an order from a route having a small amount of overlapping with other routes by using a rearranged route list as an input. Since it is easy to allocate a route having a small amount of overlapping with other routes to same communication management information, the timeslot list generation device in the present example embodiment provides an advantageous effect that it is possible to more advantageously reduce a timeslot number of a timeslot list to be generated, in addition to the advantageous effects of the first example embodiment.

Third Example Embodiment

(81) [Description on Configuration]

(82) Next, a third example embodiment of the present invention is described with reference to the drawings. FIG. 8 is a block diagram illustrating a configuration example of the third example embodiment of a timeslot list generation device 100 according to the present invention.

(83) The timeslot list generation device 100 illustrated in FIG. 8 includes a shortest sparse route generation means 110 and a comprehensive timeslot allocation means 140. Unlike the timeslot list generation device 100 illustrated in FIG. 1, the timeslot list generation device 100 in the present example embodiment includes the comprehensive timeslot allocation means 140 in place of the timeslot allocation means 120.

(84) The comprehensive timeslot allocation means 140 has a function of the timeslot allocation means 120. Further, the comprehensive timeslot allocation means 140 also has a function of determining a timeslot list having a smallest timeslot number among all generatable timeslot lists.

(85) [Description on Operation]

(86) In the following, an operation of the timeslot list generation device 100 in the present example embodiment is described with reference to FIG. 9. FIG. 9 is a flowchart illustrating an operation of generation processing by the timeslot list generation device 100 in the third example embodiment.

(87) The shortest sparse route generation means 110 receives an endpoint pair list and network topology information as an input. Then, the shortest sparse route generation means 110 generates a route being a shortest route connecting between endpoints, and which does not pass through a same link simultaneously with another route as much as possible for each piece of endpoint pair information within the endpoint pair list.

(88) The shortest sparse route generation means 110 outputs a route list constituted by the generated routes (Step S310). Note that processing of Step S310 is the same as processing of Step 110 illustrated in FIG. 2.

(89) Then, the comprehensive timeslot allocation means 140 calculates timeslot numbers of all timeslot lists generatable based on the routes within the route list, respectively, and determines a timeslot list having a smallest timeslot number (Step S320).

(90) Then, the comprehensive timeslot allocation means 140 outputs the determined timeslot list. After outputting the timeslot list, the timeslot list generation device 100 terminates the generation processing.

(91) Next, an operation of the comprehensive timeslot allocation means 140 in the present example embodiment is described with reference to FIG. 10. FIG. 10 is a flowchart illustrating an operation of timeslot list generation processing by the comprehensive timeslot allocation means 140. Specifically, processing of Step S321 to Step S329 illustrated in FIG. 10 corresponds to processing of Step S320 illustrated in FIG. 9.

(92) The comprehensive timeslot allocation means 140 receives a route list as an input. The comprehensive timeslot allocation means 140 generates all patterns on route permutation by rearranging the routes within the route list (Step S321).

(93) The comprehensive timeslot allocation means 140 generates a permutation list including all patterns on route permutation. Then, the comprehensive timeslot allocation means 140 initializes a preliminary smallest timeslot number and a preliminary timeslot list (Step S322). After initialization, the comprehensive timeslot allocation means 140 enters a generation loop (Step S323).

(94) Then, the comprehensive timeslot allocation means 140 extracts one permutation from the permutation list. The comprehensive timeslot allocation means 140 allocates the extracted permutation, in other words, routes within the rearranged route list to communication management information in such a manner that the routes do not pass through a same link during a same time zone (Step S324). Note that processing of Step S324 is the same as processing of Step S120 illustrated in FIG. 2.

(95) Then, the comprehensive timeslot allocation means 140 calculates a timeslot number of a timeslot list generated in Step S324 (Step S325). The comprehensive timeslot allocation means 140 checks whether or not the calculated timeslot number is smaller than the preliminary smallest timeslot number (Step S326).

(96) When the calculated timeslot number is equal to or larger than the preliminary smallest timeslot number (No in Step S327), the comprehensive timeslot allocation means 140 performs processing of Step S324 again.

(97) When the calculated timeslot number is smaller than the preliminary smallest timeslot number (Yes in Step S327), the comprehensive timeslot allocation means 140 updates the preliminary smallest timeslot number to the calculated timeslot number. Further, the comprehensive timeslot allocation means 140 updates the preliminary timeslot list to the timeslot list generated in Step S324 (Step S328). After updating, the comprehensive timeslot allocation means 140 performs processing of Step S324 again.

(98) The comprehensive timeslot allocation means 140 repeats processing of Step S324 to Step S328 during a period when a route list which is not processed within the permutation list is present, in other words, until the permutation list becomes empty. When all the route lists within the permutation list are processed, the comprehensive timeslot allocation means 140 exits from the generation loop (Step S329), and terminates the timeslot list generation processing.

(99) Note that the comprehensive timeslot allocation means 140 may determine a timeslot list having a smallest timeslot number by a method other than a method using a preliminary smallest timeslot number as illustrated in FIG. 10.

(100) [Description on Advantageous Effects]

(101) Next, advantageous effects of the present example embodiment are described. The comprehensive timeslot allocation means in the present example embodiment calculates timeslot numbers of all timeslot lists generatable based on routes within a route list. Thus, since it is possible to generate a timeslot list having a smallest timeslot number, the timeslot list generation device in the present example embodiment is able to more appropriately allocate a route within a given route list to communication management information, as compared with the first and second example embodiments.

Fourth Example Embodiment

(102) In the following, a fourth example embodiment of the present invention is described with reference to the drawings. FIG. 11 is an explanatory diagram illustrating an example of a network topology in a range where communication as a processing target in the present example embodiment is performed. The network topology illustrated in FIG. 11 is identical to a network topology illustrated in FIG. 22. Also in the present example embodiment, in order to simplify description, one packet is handled as one flit.

(103) FIG. 12 is an explanatory diagram illustrating an example of an endpoint pair list to be input to a shortest sparse route generation means 110 in the present example embodiment. The endpoint pair list illustrated in FIG. 12 is constituted by endpoint pair information. The endpoint pair information is constituted by input terminals, input ports, output terminals, and output ports.

(104) An input terminal indicates a terminal serving as a start point of communication. An input port indicates a port of an input terminal serving as a start point of communication. An output terminal indicates a terminal serving as a finish point of communication. An output port indicates a port of an output terminal serving as a finish point of communication. Note that, in order to simplify description, in the present example embodiment, an input port and an output port are not considered.

(105) [Description on Operation]

(106) In the following, an operation of a timeslot list generation device 100 in the present example embodiment is described with reference to FIG. 2, FIG. 7, and FIG. 9.

(107) The shortest sparse route generation means 110 receives the endpoint pair list illustrated in FIG. 12, and the network topology information illustrated in FIG. 11 as an input. Then, the shortest sparse route generation means 110 generates a route list constituted by shortest routes generated based on each piece of endpoint pair information constituting the input endpoint pair list (Step S110, Step S210, Step S310).

(108) FIG. 13 is an explanatory diagram illustrating an example of a route list to be generated by the shortest sparse route generation means 110 in the present example embodiment. The route list is constituted by route information. The route information is constituted by a route name, and an n-th link (where n is a natural number). Each link is a link through which a route associated with a route name passes. Further, an n-th link is a link through which a route passes from a start point to a finish point at an n-th time.

(109) Specifically, [V(13)>V(3)@d=1] being a first link of a path 1 means that the first (d=1) link of the path 1 is a link between a terminal 13(V(13)) and a switch 3 (V(3)). Further, a portion indicated by an oblique line within route information means that a link associated with the portion is not present. Specifically, a link immediately preceding a portion indicated by an oblique line is a link through which a route passes at a last time. Note that an order of pieces of endpoint pair information illustrated in FIG. 12 does not coincide with an order of pieces of route information illustrated in FIG. 13.

(110) The timeslot allocation means 120 in the first example embodiment generates a timeslot list, in which routes within a route list are all allocated by using the route list illustrated in FIG. 13 as an input (Step S120).

(111) FIG. 14 is an explanatory diagram illustrating an example of a timeslot list to be generated by a timeslot allocation means 120 in the present example embodiment. Further, FIG. 15 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 14.

(112) A time when overall communication to be performed based on the timeslot list illustrated in FIG. 14 is finished is a time corresponding to a timeslot 8 being a time when communication using a link switch 9.fwdarw.terminal 19 indicated by a mark x is finished, when the time chart illustrated in FIG. 15 is referred to. Specifically, a timeslot number of the timeslot list illustrated in FIG. 14 is eight. A timeslot number of the timeslot list illustrated in FIG. 14 is reduced to eight, as compared with a timeslot number of the timeslot list illustrated in FIG. 26, which is 23.

(113) Next, an operation of the timeslot list generation device 100 in the second example embodiment is described. The descending order distance route rearranging means 130 in the second example embodiment rearranges routes within a route list in the descending order of sum of distances to other routes by using the route list illustrated in FIG. 13 as an input (Step S220).

(114) FIG. 16 is an explanatory diagram illustrating an example of a rearranged route list to be generated by a descending order distance route rearranging means 130 in the present example embodiment. As compared with the route list illustrated in FIG. 13, routes are rearranged in an order of path 9, path 8, path 7, path 6, path 5, path 4, path 3, path 2, and path 1.

(115) Then, the timeslot allocation means 120 in the second example embodiment generates a timeslot list, in which routes within a route list are all allocated by using the route list illustrated in FIG. 16 as an input (Step S230).

(116) FIG. 17 is an explanatory diagram illustrating another example of a timeslot list to be generated by the timeslot allocation means 120 in the present example embodiment. Further, FIG. 18 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 17.

(117) A time when overall communication to be performed based on the timeslot list illustrated in FIG. 17 is finished is a time corresponding to a timeslot 8, when the time chart illustrated in FIG. 18 is referred to. The time corresponding to the timeslot 8 is a time when communication using a link switch 9.fwdarw.terminal 19 indicated by a mark .diamond-solid. in FIG. 18, and communication using a link switch 7.fwdarw.terminal 17 indicated by a mark x in FIG. 18 are finished.

(118) Specifically, a timeslot number of the timeslot list illustrated in FIG. 17 is eight. A timeslot number of the timeslot list illustrated in FIG. 17 is reduced to eight, as compared with a timeslot number of the timeslot list illustrated in FIG. 26, which is 23.

(119) Next, an operation of the timeslot list generation device 100 in the third example embodiment is described. A comprehensive timeslot allocation means 140 in the third example embodiment uses the route list illustrated in FIG. 13 as an input. The comprehensive timeslot allocation means 140 calculates timeslot numbers of all timeslot lists generatable based on routes within a route list, respectively, and determines a timeslot list having a smallest timeslot number (Step S320).

(120) FIG. 19 is an explanatory diagram illustrating an example of a timeslot list to be generated by a comprehensive timeslot allocation means 140 in the present example embodiment. Further, FIG. 20 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 19. Note that, in FIG. 19, only communication routes in timeslots 0 to 2 are exemplified.

(121) A time when overall communication to be performed based on the timeslot list illustrated in FIG. 19 is finished is a time corresponding to a timeslot 7, when the time chart illustrated in FIG. 20 is referred to. The time corresponding to the timeslot 7 is a time when communication using a link switch 9.fwdarw.terminal 19 indicated by a mark .diamond-solid. in FIG. 20, and communication using a link switch 8.fwdarw.terminal 18 indicated by a mark x in FIG. 20 are finished.

(122) Specifically, a timeslot number of the timeslot list illustrated in FIG. 19 is seven. A timeslot number of the timeslot list illustrated in FIG. 19 is further reduced to seven, as compared with timeslot numbers of the timeslot lists illustrated in FIG. 14 and FIG. 17, which are eight.

(123) Whereas a time required for generating the timeslot lists illustrated in FIG. 14 and FIG. 17 is about 0.1 second, a time required for generating the timeslot list illustrated in FIG. 19 is about seven seconds. Specifically, a time relating to generation processing by the timeslot list generation device 100 in the third example embodiment is long, as compared with the first and second example embodiments.

(124) Further, it is expected that, as a scale of communication network in which communication is performed increases, a computation time required for generating a timeslot list further increases. Therefore, it is preferable for a user to select a configuration of a timeslot list generation device 100 to be used depending on a scale of communication network, in which communication is performed.

(125) Note that the timeslot list generation device 100 in each of the example embodiments is implemented by a central processing unit (CPU) for executing processing in accordance with a program stored in a storage medium, for example. Specifically, the shortest sparse route generation means 110, the timeslot allocation means 120, the descending order distance route rearranging means 130, and the comprehensive timeslot allocation means 140 are implemented by a CPU for executing processing in accordance with program control, for example.

(126) Further, each component in the timeslot list generation device 100 may be implemented by a hardware circuit.

(127) Next, an outline of the present invention is described. FIG. 21 is a block diagram illustrating an outline of a communication management list generation device according to the present invention. A communication management list generation device 20 according to the present invention is a communication management list generation device for generating a communication management list constituted by communication management information including time information associated with a predetermined time, and communication information indicating communication processing which is started at the predetermined time and which does not use a same route simultaneously. The communication management list generation device 20 includes a determination means 21 (e.g. the timeslot allocation means 120) for determining each piece of communication management information in an ascending order of time associated with the time information regarding whether or not communication processing information is addable to communication information, and an addition means 22 (e.g. the timeslot allocation means 120) for adding communication processing information to communication information of communication management information determined to be addable at a determination stage by the determination means 21.

(128) According to the aforementioned configuration, the communication management list generation device is able to generate a timeslot list with which communication free of blocking is performed at a shorter time interval.

(129) Further, the determination means 21 may determine whether or not communication processing information is addable in a descending order of sum of distances between a shortest route to be used with respect to a plurality of communication processings, and a shortest route to be used by other communication processings.

(130) According to the aforementioned configuration, the communication management list generation device is able to more advantageously reduce a timeslot number of a timeslot list to be generated.

(131) Further, the communication management list generation device 20 may include a measuring means (e.g. the comprehensive timeslot allocation means 140) for measuring a time required for overall communication processing to be performed by using a communication management list generated by adding all pieces of communication processing information as an addition target. The measuring means may output a communication management list having a smallest required time among all patterns on a communication management list to be generated based on communication processing information as an addition target.

(132) According to the aforementioned configuration, the communication management list generation device is able to more appropriately allocate a route within a route list to communication management information.

(133) Further, communication processing information may be shortest route information, in which a sum of distances to a shortest route to be used by other communication processing is maximum among all patterns on a shortest route to be used by communication processing.

(134) According to the aforementioned configuration, the communication management list generation device is able to more easily allocate a route within a route list to communication management information.

(135) Further, the communication management list generation device 20 may include a shortest sparse route generation means (e.g. the shortest sparse route generation means 110) for generating shortest route information as communication processing information by using network topology information and an endpoint pair list as an input. Further, the shortest sparse route generation means may generate a route list being a set of shortest routes, in which passing links do not overlap each other.

(136) According to the aforementioned configuration, the communication management list generation device is able to generate communication route information, in which communication routes do not share a same link simultaneously as much as possible.

(137) While the invention has been particularly shown and described with reference to example embodiments thereof, the invention is not limited to these embodiments. It will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the claims.

(138) This application is based upon and claims the benefit of priority from Japanese patent application No. 2015-202276, filed on Oct. 13, 2015, the disclosure of which is incorporated herein in its entirety by reference.

INDUSTRIAL APPLICABILITY

(139) The present invention is advantageously applicable to design support, in which a route problem or a band problem is detected at the time of designing when a highly reliable virtual communication network is configured. Further, the present invention is also advantageously applicable to setting verification, in which a route problem or a band problem that occurs by erroneous setting is detected, when a highly reliable virtual communication network is configured.

REFERENCE SIGNS LIST

(140) 1 to 9 Switch 11 to 13, 17 to 19 Terminal 20 Communication management list generation device 21 Determination means 22 Addition means 100, 900 Timeslot list generation device 110 Shortest sparse route generation means 120 Timeslot allocation means 130 Descending order distance route rearranging means 140 Comprehensive timeslot allocation means 910 Shortest route generation means 920 Segment dividing means 930 Segment timeslot allocation means