JP2000183914A - ATM cell queue read scheduling method and apparatus - Google Patents

Abstract

(57) [Summary] [Problem] To suppress fluctuation of a cell transmission interval within a specified range,
A method and apparatus for controlling a read schedule of an ATM cell queue in which a transmission band is guaranteed and a plurality of connections can be multiplexed. A plurality of ATs multiplexed on the same output line.
For the M cell queue, read timing is defined in a read schedule table, and ATM cells are read from each cell queue according to the schedule table. When a cell queue of a new connection occurs, a read timing candidate point is selected at a read interval according to the requested bandwidth, and the candidate point is assigned to each candidate point within the allowable range of the cell transmission interval fluctuation. Modify the read timing position so that the density of the timing position is the most averaged.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an ATM cell queue read scheduling method and apparatus, and more particularly to an ATM node apparatus in which a plurality of ATM connections are multiplexed on the same output line. The present invention relates to an ATM cell read scheduling method and apparatus for reading an ATM cell queue while securing a band.

[0002]

2. Description of the Related Art In a node device (for example, an ATM switch) constituting an ATM network, ATM cells input from a plurality of input lines are switched to one of output lines in accordance with routing information included in each cell header. You. ATM cells received from each input line are:
In the node, each cell is queued in an ATM cell queue for each connection associated with the output line, and is transmitted to the output line one cell at a time at a predetermined read timing periodically allocated to each output line.

FIG. 7 is a schematic diagram of a conventional cell multiplexing unit for reading out ATM cells from a plurality of ATM cell queues formed in an ATM switch by a weighted round robin method and multiplexing a plurality of connections on the same output line. A simple configuration is shown. 1 (1-1, 1-2,...) Are ATM cell queues formed corresponding to connections, 2 is an ATM cell queue reading section, and 3 is an ATM cell queue reading schedule table (bandwidth management table) formed in a memory. Is shown. The queue readout schedule table 3 includes a plurality of time slots corresponding to the cell readout timing on each output line.

In the weighted round robin method, time slots on the queue readout schedule table 3 are allocated to a plurality of ATM cell queues to be multiplexed on the same output line at a frequency corresponding to each required bandwidth.
The ATM cell queue reading unit 2 sequentially scans the queue reading schedule table 3 and accesses the ATM cell queue 1-i indicated by the cell queue identifier in the time slot in which the cell queue identifier (or connection identifier) has been registered. In the following description, a time slot assigned to each cell queue is called an entry point.

According to the cell queue readout of the weighted round robin method, at the time of setting each connection, the entry points in the readout schedule table 3 are set so that the queue readout number per unit time matches the required bandwidth of each ATM connection. Is assigned, ATM cell transfer can be performed in a form that guarantees a transmission band for each connection. Also, by assigning entry points so that the access interval is constant for each ATM cell queue, the cell transmission interval can be kept constant for each ATM connection. As for the ATM switch adopting the ATM cell queue readout scheduler of the weighted round robin method, for example, “Weighted
Round-Robin Cell Multiplexing in a General-purpos
e ATM Switch Chip "(IEEE JSAC. Vol. 9, No. 8, 199
It is described in 1).

[0006]

However, in the above-described ATM cell queue reading of the weighted round robin method, when the number of connections to be multiplexed on the same output line increases, a transmission band is secured for each connection and cell transmission is performed. It is difficult to keep the interval constant. Because
In order to secure a desired bandwidth with a constant cell transmission interval, it is necessary to assign an entry point to each connection (ATM cell queue) at predetermined intervals, but bandwidths have already been allocated to some connections. If a bandwidth allocation request to a new connection is issued in the state described above, a situation arises in which the entry point at an ideal timing for the new connection has already been allocated to another connection and cannot be used.

An object of the present invention is to provide an ATM cell queue read scheduling method and apparatus which can increase the number of connections multiplexed on the same output line. It is another object of the present invention to provide an ATM cell queue read scheduling method and apparatus capable of increasing the number of connections that can be multiplexed on the same output line while suppressing fluctuations in cell transmission intervals within an allowable range. Still another object of the present invention is to provide an ATM cell multiplexing apparatus capable of multiplexing and transmitting ATM cells by suppressing fluctuations of cell intervals within an allowable range and effectively utilizing a transmission band of an output line. is there.

[0008]

To achieve the above object, the present invention provides an ATM cell queue read scheduling method, comprising the steps of: (a) referring to a schedule table when a new connection occurs; A plurality of time slots arranged at predetermined intervals determined by a band are selected as entry candidate points. (B) A predetermined sampling range is set for each of the entry candidate points, and an empty state time included in the sampling range is set. From among the slots, a time slot that is within the fluctuation range of the transmission cell interval and consequently averages the density of closed time slots within the sampling range is selected as an optimal entry point, and (c) Assign the time slot corresponding to the optimal entry point in the schedule table to the new cell queue. And wherein the Rukoto.

More specifically, in step (a), a plurality of time slots arranged at predetermined intervals starting from an empty time slot are selected as entry candidate points. In step (b), for example, A predetermined sampling range set for each entry candidate point is determined by a plurality of time slots within the transmission cell interval fluctuation allowable range set for the entry candidate point and a correlation set for each time slot within the allowable range. A time slot that includes a plurality of time slots in the range and has a minimum closed time slot density calculated in each of the correlation ranges is selected as an optimal entry point from the empty time slots in the allowable range.

In a preferred embodiment of the present invention, in the step (a), a plurality of sets each including a plurality of time slots arranged at predetermined intervals determined by the required bandwidth of the new connection, starting from different time slots. In the step (c), a set having the most uniform entry point interval is selected from a plurality of sets of optimum entry points obtained with respect to the plurality of sets of entry candidate points, A time slot corresponding to the selected entry point in the schedule table is assigned to the new cell queue. Further, in step (b), a bit pattern is generated in which the occupied state of each time slot within the sampling range is indicated by “1” and “0” bits, and the density of each of the correlation ranges is determined based on the bit pattern. Ask for.

An ATM cell multiplexer according to the present invention comprises:
(A) It has a plurality of cell queues formed corresponding to the connection, and (B) has a ring table composed of a plurality of time slots, and for a plurality of connections multiplexed on the same line, the ring table corresponding to the line (C) means for reading storage cells from the plurality of cell queues based on the read schedule table, and (D) a new read schedule table for designating read timing of cells from the cell queue in the time slot of And a schedule control means for updating the schedule table so as to designate a cell read timing from a new cell queue corresponding to the connection when the connection has occurred. When this occurs, refer to the above schedule table and Means for selecting, as entry candidate points, a plurality of time slots arranged at predetermined intervals determined by the required bandwidth of the connection in a corresponding ring table, and including, within each of the entry candidate points, a predetermined sampling range. From the empty time slots to be transmitted, the transmission cell interval is within the fluctuation range, and
Means for selecting a time slot for averaging the density of the closed time slots within the sampling range as an optimum entry point, wherein the schedule control means is configured to determine the optimum entry point of the ring table. The identifier of a new cell queue corresponding to the connection is registered in each time slot corresponding to.

[0012]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below with reference to the drawings. FIG. 1 shows an embodiment of an ATM cell queue readout control device according to the present invention. In the figure, 1
(1-1, 1-2,...) Are ATM cell queues, 2 is a cell read from the ATM cell queue, and a signal line OUT
, An ATM cell queue reading schedule table (bandwidth control table) 30 updated in accordance with the present invention, and 4 a cell queue reading schedule control unit.

The schedule table 30 has a ring table structure having a predetermined number of entry points (time slots) per one output line. When the signal line OUT is the output line as it is, the schedule table 30 may have a ring table for one line.
A separation circuit (not shown) is connected to the end of the signal line OUT,
In the case of a switch structure in which the ATM cells read out to the signal line OUT are sequentially distributed to a plurality of output lines by the separation circuit, a plurality of ring tables corresponding to the output lines are formed in the schedule table 30.

In the latter case, the plurality of ring tables are sequentially selected in synchronization with the output line scanning in the separation circuit, and time slots are sequentially and cyclically scanned within the selected ring table. The cell queue identifier at the entry point is read, and the ATM cell queue reading unit 2
Sequentially reads cells from the ATM cell queue corresponding to the cell queue identifier. If there are N output lines, N
Independent ring tables are required.
By multiplexing each time slot in one ring table on a one-dimensional time axis, it is apparently one relatively long ring table, and (j + Nm) ) The cell queue may be designated by a time slot (where m is an integer).

The cell queue read schedule control unit 4 includes a schedule table update control unit 5, a schedule sample unit 6, and a queue read timing determination unit 7. When a bandwidth allocation request to one output line is generated for a new connection, the schedule table update control unit 5 specifies a ring table corresponding to the output line based on the requested bandwidth information input from the outside, An entry candidate point is searched at a predetermined slot interval determined by the required bandwidth.

As shown in FIG. 2, a plurality of entry points k1, k2, k3 arranged at an ideal arrangement interval (slot interval) determined by a required bandwidth in the ring table 31 for each output line, as shown in FIG. ,. . . Consists of Assuming that the scanning period that goes around the ring table 31 corresponds to the bandwidth w, the number K of entry points required to satisfy the required bandwidth W is K = W / w. Also, the i-th
The position of the entry point ki is defined as ki when the ideal arrangement interval between entry points determined by the size (total number of entry points) N of each ring table is Δk (= N / K).
= L + Δk × (i−1). Here, L indicates the position of the first entry point k1 as a start point.

The schedule table update control unit 5 selects a plurality of sets of entry candidate points having different start points with a time slot in an empty state as a start point (entry point k1), and determines each entry candidate point in each set. A predetermined range (sampling range) at the center is sequentially instructed to the schedule sampling unit 6.

The schedule sample unit 6 refers to the ring table 31 for a plurality of time slots within the sampling range centered on each of the above entry candidate points, and determines whether or not these time slots have already been allocated to another connection. A bit pattern represented by “1” and “0” bits is generated. For example, as shown in FIG. 2, the bit pattern of the entry candidate point k2 is such that the entry candidate point k2 is set as the center point (ideal arrangement position) P8 and the entry points P5 to P1 within the fluctuation tolerance of the cell transmission interval.
2 and a time slot area including entry points P1 to P4 and P13 to P16 in a correlation range for weight calculation described later, as a sampling range 32, and the occupancy state of each entry point is represented by bits. . The bit pattern extracted within the sample range 31 is supplied to the queue read timing determination unit 7 as sample data.

Based on each sample data supplied from the schedule sampler 6, the queue read timing determiner 7 selects one of the vacant entry points within the permissible fluctuation range, and consequently, within each sample range. Of the closed state entry points are distributed and the optimum entry point is selected such that the density of the closed state entry points is most averaged. The optimum entry point within each of the sampling ranges selected by the queue read timing determination section 7 is provided to the schedule table update control section 5 as optimum timing position information.

The schedule table update control unit 5 compares the optimum timing position information obtained from the queue read timing determination unit 7 with respect to a plurality of sets of entry candidate points (sampling ranges) having different start points, and selects an entry from among them. A group in which the points are arranged at the most uniform intervals is selected and used as the allocation entry point for the new connection.
The cell queue identifier is registered in the TM cell queue reading schedule table 3.

In the above embodiment, for a plurality of sets of entry candidate points having different starting points selected from the cell queue readout schedule table, a sampling range including a plurality of entry points located within respective transmission allowable ranges is set, and as a result, In this case, an entry point optimized so that the closed state entry points are averaged and arranged in a distributed manner is selected, and a set having the averaged entry point interval is selected from the set of these optimized entry points. A selection is made to assign read timing to the additional cell queue. For this reason,
In the ring table, empty time slots are left scattered on average, so that even if there is a request for multiplexing connections one after another on the same output line, the transmission interval fluctuations for new connections. Bands can be allocated in a form within an allowable range, and it is possible to respond to various band allocation requests.

FIG. 3 shows the configuration of the queue read timing determination section 7. Queue read timing determination unit 7
A density calculation unit 71 for calculating a closed state entry point density within a predetermined correlation range for each entry point within the allowable arrangement range based on the sample data provided from the schedule sample unit 6; Based on the density information calculated by the calculation unit 71, an optimum position determination unit 72 that determines an entry point of an optimum position where the block state entry points have the most averaged array and outputs the entry point as optimum timing position information.
It is composed of

In the density calculating section 71, for example, as shown by specifying a range with a horizontal arrow in FIG. 2, the correlation to be considered in the density calculation for each of the entry points P5 to P12 within the allowable arrangement range. The range is defined, and each entry point P5
When ~ P12 is selected as a candidate point for band allocation, the density of closed entries within each correlation range (or the degree of array averaging) in relation to entry points which are already closed within the correlation range. (Weight) indicating what happens to
Is calculated. Weight N when entry point P is set as a candidate point
p can be calculated by the following equation, for example.

[0024]

Np = Σi W [Dp-i] · δ [i]
(Where i ≠ P) where i is a suffix indicating each entry point within the density correlation range, Dp-i is the distance between the candidate point P and the entry point i,
W [D] is the weight corresponding to the distance D, δ [n] is the position n
Has the value “1” when the entry is in the closed state, and has the value “0” when the entry is in the empty state. Note that the weight W [D] is equal to the distance r (=
As a function of Dp-i), for example, 1 / r or 1 / r · r
Alternatively, various functional forms such as a higher order form of 1 / r can be adopted.

The optimum position judging section 72 includes the density calculating section 7
By comparing the weight Np of each candidate point calculated in step 1, the weight Np
Is selected, and is output as the optimal timing position information.

FIG. 4 shows the configuration of the schedule table update control unit 5. The schedule creation control unit 5 refers to the read schedule table 3 based on the requested transmission band information,
On a ring table corresponding to an output line to which a new connection is to be multiplexed, a set of entry candidate points corresponding to a required band is extracted, and a sampling range determining unit 51 for instructing a sampling range to a schedule sample unit 6; Based on the optimum timing position information provided by the determination unit 7, the set with the most uniform entry point interval is selected from the set of entry candidate points of the optimum timing obtained in a plurality of sets of sampling ranges having different start points. And a bandwidth allocating unit 52 for selecting and allocating to the ATM cell queue of the new connection.

In the above embodiment, the sampling range determination unit 51 sets the sampling range for each entry candidate point. However, the sampling range determination unit 51 notifies the schedule sample unit 6 of only the entry candidate points, and The sampling section 6 may set a predetermined sampling range for each candidate point to generate a bit pattern.

FIG. 5 is a flowchart showing a series of processes executed by the cell queue readout schedule control unit 4 described above. Step 20 is a sampling position determination process performed by the sampling range determination unit 51, and step 21 is A scheduling sampling process performed by the schedule sampling unit 6; step 22 is a process of determining an optimal position (a position of an averaged entry candidate point) performed by the queue read timing determination unit 7;
Shows the process of determining the optimum entry candidate point and allocating the cell queue readout timing performed by the band allocation unit 52.

FIG. 6 shows a modification of the present invention in which a timing position range limiting section 8 is added to the cell queue reading schedule control section 4 of FIG. The timing position range limiting unit 12 includes the density calculating unit 7 of the queue read timing determining unit 7.
1, information for limiting the range of existence of candidate points to be subjected to density calculation is given. For example, FIG.
In, the density calculation targets entry candidate points within the allowable arrangement range, but each new connection requesting a band has a unique priority, and the allowable range of the fluctuation of the cell interval is not necessarily the same. In the present embodiment, the range of existence of candidate points to be subjected to density calculation is made variable for each connection so that an optimum entry point can be selected within a specified allowable range.

The cell queue readout schedule control described above according to the present invention can be realized by a dedicated hardware device or a program executed by a microprocessor.

[0031]

As is apparent from the above description, according to the present invention, when assigning the readout timing of the cell queue to the readout schedule table (bandwidth management table), it is located near an ideal entry point determined by the required bandwidth. Since the sampling range is set and the entry point within the permissible fluctuation range and the closed state entry density is averaged is selected, the bandwidth is guaranteed and the fluctuation of the cell transmission interval is kept within the permissible range. Can multiplex a large number of connections.

[Brief description of the drawings]

FIG. 1 is a block diagram showing one embodiment of a cell queue readout schedule control unit according to the present invention.

FIG. 2 is a diagram showing a relationship between a read timing position on a ring table 31 and a sampling area 32 referred to in an optimum position determination.

FIG. 3 is a block diagram showing a configuration of a queue read timing determination unit 7;

FIG. 4 is a block diagram showing a configuration of a schedule table update control unit 5;

FIG. 5 is a flowchart showing a procedure of cell queue readout schedule control according to the present invention.

FIG. 6 is a block diagram showing a modification of the cell queue readout schedule control unit in FIG. 1;

FIG. 7 is a block diagram showing a main part of a conventional ATM switch employing a weighted round-robin ATM cell queue readout.

[Explanation of symbols]

1: ATM cell queue 2: ATM cell queue readout unit 3, 30: ATM cell queue readout schedule table 4: Cell queue readout schedule control unit 5: Schedule table update control unit 6: Schedule sample unit 7: Queue readout timing determination unit 8: Timing position range Limiting part 51: Sampling range determining part 52: Band allocating part 71: Density calculating part 72: Optimal position determining part

 ──────────────────────────────────────────────────続 き Continuing from the front page (72) Inventor Akihiro Hiroshi 216 Totsuka-cho, Totsuka-ku, Yokohama-shi, Kanagawa Prefecture Inside the Hitachi, Ltd.Information and Communications Division (72) Inventor Masanobu Kobayashi 216 Totsuka-cho, Totsuka-ku, Yokohama-shi, Kanagawa Prefecture Hitachi, Ltd.Information and Communication Division (72) Inventor Akihiko Tanaka 216 Totsuka-cho, Totsuka-ku, Yokohama-shi, Kanagawa Prefecture 216-cho, Hitachi, Ltd.Information and Communication Division, Hitachi, Ltd. (72) Inventor Shunsuke Tsutsumi 3-9-1-2 Nishi-Shinjuku, Shinjuku-ku, Tokyo Inside Nippon Telegraph and Telephone Corporation (72) Inventor Manabu Yoshino, Nishi-Shinjuku, Shinjuku-ku, Tokyo 3-chome 19-2 Nippon Telegraph and Telephone Corporation F-term (reference) 5K030 GA08 GA11 HA10 HB15 JA01 KA01 KA03 KA13 KX13 L C08 LE06 MA13

Claims (8)

[Claims] 1. A plurality of cell queues corresponding to connections multiplexed on the same line are assigned respective read timings in a read schedule table comprising a plurality of time slots, and a new connection multiplexed on the line is generated. In the ATM cell queue read scheduling method in which cell read timing from a new cell queue corresponding to the connection is assigned to an empty time slot of the schedule table, (a) referring to the schedule table, Selecting a plurality of time slots arranged at predetermined intervals determined by the required bandwidth as entry candidate points; and (b) setting a predetermined sampling range for each of the entry candidate points and including the sampling range within the sampling range. Empty state Selecting a time slot that is within the fluctuation range of the transmission cell interval and that results in averaging the density of closed time slots in the sampling range from among the time slots, as an optimal entry point; c) allocating a time slot corresponding to the optimum entry point in the schedule table to the new cell queue. 2. In the step (b), a predetermined sampling range set for each of the entry candidate points is:
A plurality of time slots within a permissible range of transmission cell interval fluctuations set for the entry candidate point, and a plurality of time slots within a correlation range set for each time slot within the permissible range; 2. The ATM cell queue read scheduling according to claim 1, wherein a time slot having a minimum closed time slot density calculated in each of the correlation ranges is selected as an optimum entry point from the empty time slots. Method. 3. The method according to claim 1, wherein in said step (a), a plurality of time slots arranged at predetermined intervals starting from an empty time slot are selected as said entry candidate points. 2. A method for scheduling reading of an ATM cell queue according to the above. 4. A plurality of cell queues corresponding to connections multiplexed on the same line are assigned respective read timings in a read schedule table comprising a plurality of time slots, and a new connection multiplexed on the line is generated. Then, in the ATM cell queue read scheduling method in which the cell read timing from the new cell queue corresponding to the connection is assigned to an empty time slot in the schedule table, (a) the schedule tables are different from each other. Selecting a plurality of sets of entry candidate points consisting of a plurality of time slots arranged at predetermined intervals determined by the required bandwidth of the new connection, starting from the time slots; (b) for each of the above set of entry candidate points; A predetermined sump And setting the density of closed time slots within the permissible fluctuation range of the transmission cell interval from the empty time slots included in the sampling range, and consequently, the density of the closed time slots within the sampling range. Selecting a time slot to be averaged as an optimum entry point; and (c) selecting a set with the most uniform entry point interval from a plurality of sets of optimum entry points obtained for the plurality of sets of entry candidate points. Selecting and allocating a time slot corresponding to the selected entry point in the schedule table to the new cell queue. 5. In the step (b), a predetermined sampling range set for each of the entry candidate points is:
A plurality of time slots within a permissible range of transmission cell interval fluctuations set for the entry candidate point, and a plurality of time slots within a correlation range set for each time slot within the permissible range; 5. The ATM cell queue read scheduling according to claim 4, wherein a time slot having a minimum closed time slot density calculated in each of the correlation ranges is selected as an optimum entry point from the empty time slots. Method. 6. In the step (b), the idle state of each time slot within the sampling range is set to “1”,
6. The ATM cell queue read scheduling method according to claim 5, wherein a bit pattern represented by "0" bits is generated, and the density of each of the correlation ranges is obtained based on the bit pattern. 7. A reading schedule table comprising a plurality of time slots, wherein said time slots are allocated to a plurality of cell queues corresponding to connections in accordance with respective bands, and said schedule table is cyclically scanned to thereby read each of said cell queues. ATM to control cell reading from memory
Means for selecting, as a candidate entry point, a plurality of time slots arranged at predetermined intervals determined by the required bandwidth of the connection by referring to the schedule table when a new connection occurs, For each of the entry candidate points, from the empty time slots included in the predetermined sampling range, the transmission time interval is within the fluctuation tolerance of the transmission cell interval, and, as a result, the closed time slot within the sampling range is obtained. Means for selecting a time slot for averaging the density as an optimum entry point; and registering a new cell queue identifier corresponding to the connection in each time slot corresponding to the optimum entry point in the schedule table. ATM characterized by having means of Reading scheduling apparatus of Rukyu. And a ring table including a plurality of cell queues formed corresponding to the connection and a plurality of time slots.
For a plurality of connections multiplexed on the same line, a read schedule table specifying the timing of reading a cell from a cell queue in a time slot on a ring table corresponding to the line, and the plurality of connections based on the read schedule table. And a schedule control means for updating the schedule table to designate a cell read timing from a new cell queue corresponding to the new connection when a new connection has occurred. In the ATM cell multiplexer, when a new connection occurs, the schedule control means refers to the schedule table, and is arranged in a ring table corresponding to the connection at a predetermined interval determined by a required bandwidth of the connection. Multiple ties Means for selecting a slot as an entry candidate point, for each of the above-mentioned entry candidate points, from empty state time slots included in a predetermined sampling range, within a permissible fluctuation range of the transmission cell interval, and Means for selecting a time slot for averaging the density of closed time slots within the sampling range as an optimal entry point, wherein the schedule control means comprises: An ATM cell multiplexing apparatus, wherein an identifier of a new cell queue corresponding to the connection is registered in each time slot corresponding to (1).