Patent ID: 8379663

Claim:
A time slot allocation method executed by a computer, wherein said computer is capable of accessing a slot information storage device storing, for each combination of a source node and a destination node in a network, a number of time slots to be allocated to packet transmission from the source node to the destination node, a priority storage device storing, for each said combination, an allocation priority, a link information storage device storing, for each said time slot, utilization states of links between nodes in said network, an allocation information storage device and a storage device, and said time slot allocation method comprising: judging, for each certain combination of the source node and the destination node, for which a number of time slots stored in said slot information storage device is equal to or greater than 1, whether or not certain time slots exist that are capable of forming a route from the source node to the destination node by unused links for which said utilization state represents being unused in said link information storage device among said links between said nodes; for each said certain combination judged, at said judging, that said certain time slots exist that are capable of forming said route by said unused links, identifying, for each said certain time slot, a shortest route among routes formed by said unused links, calculating an evaluation value by applying to a predetermined evaluation function, a number of hops in said shorted route, said allocation priority stored in association with a corresponding certain combination in said priority storage device and a number of links whose utilization state represents being used in a corresponding certain time slot in said link information storage device, and storing the calculated evaluation value into said storage device in association with the source node, the destination node, the shortest route and an identifier of the certain time slot; and identifying a maximum evaluation value among said calculated evaluation values stored in said storage device, and storing into said allocation information storage device, slot allocation information including the source node, the destination node, the shortest route and the identifier of the certain time slot, which are stored in said storage device in association with the maximum evaluation value.