JP4356565B2 - Distributed frame readout scheduling circuit - Google Patents

Description

The present invention provides a switch on the network, when the line concentrator or multiplexing a plurality of connections, relates to a frame read scheduling circuitry that determines the order of reading frame with each connection. In particular, while ensuring fairness relates to a frame read scheduling circuitry to accommodate high-volume traffic.

  In a switch that handles Ethernet (registered trademark) frames on a network, when multiple connections are concentrated or multiplexed, a fair bandwidth between connections based on information such as guaranteed bandwidth and priority set for each connection Is being distributed. In order to perform fair bandwidth distribution among connections, a method of giving a token that is a right to read a frame to each connection using fair read control such as WFQ (Weighted Fair Queuing) and WRR (Weighted Round Robin), There is a method of preparing FIFO buffers individually for a plurality of connections and reading out variable-length frames stored in each buffer (for example, see Non-Patent Document 1).

  As the number of connections to be accommodated in a device such as a switch increases and the bandwidth allocated to each connection increases, the total amount of traffic handled in the device also increases. In order to prevent the access bandwidth of the memory used for scheduling in the circuit from being exceeded and to perform scheduling even when the total amount of traffic handled in the device increases, each circuit block of the frame read scheduling circuit is A plurality of them are used in parallel.

  FIG. 1 is a block diagram showing an example of a conventional frame readout scheduling circuit. The configuration of FIG. 1 is referred to as a standalone type. According to FIG. 1, a bandwidth control unit 2 is prepared for each frame input unit 1. For traffic concentration and multiplexing, a method of assigning a fixed bandwidth to each bandwidth control unit 2 or a method in which the bandwidth control unit 2 and the frame output unit 3 are connected by a high-speed internal transmission path to generate a frame. A method of applying back pressure to each band control unit from the output unit 3 can be used. However, in the above method, the fairness of bandwidth allocation can be ensured between connections input to the same frame input unit, but the fairness of bandwidth allocation is ensured between connections input to different frame input units. Can not.

  FIG. 2 is a block diagram showing another example of a conventional frame readout scheduling circuit. The configuration of FIG. 2 is referred to as a multistage type. According to FIG. 2, for each frame input unit 1, a band control unit 2-0 for each output route is provided after the prepared band control unit 2. In this configuration, even if connections are input to different frame input units, the fairness of bandwidth allocation between connections can be ensured if the output route is the same. However, since it passes through the bandwidth control unit a plurality of times, the delay increases, which affects low-delay traffic such as voice. In addition, by providing a large number of bandwidth control units having a large circuit scale, the scale of the semiconductor that accommodates them increases, resulting in an increase in cost.

Yukihiro Yoshida, Yasunobu Kasahara, “Examination of bandwidth fair allocation function in Ether demultiplexer”, Shingaku Techniques, CS2002-103, November 2002

Therefore, according to the present invention, even when the total amount of traffic to be handled increases, the fairness of the allocated bandwidth between connections can be ensured while using a plurality of circuit blocks in parallel in order to avoid the limitation due to the memory access bandwidth. the frame read scheduling circuitry, and to provide without increasing the circuit scale and delay than the prior art.

According to the frame readout scheduling circuit of the present invention,
1 or more houses the connection, in a circuit for performing scheduling for the frame readout, and a plurality of frames input means corresponding to a plurality of input routes, a plurality of frames output means corresponding to a plurality of output routes A plurality of output route selection means provided corresponding to each of the plurality of frame input means ; a plurality of band control means provided corresponding to each combination of the plurality of frame input means and the plurality of frame output means; And a bandwidth allocating means. The frame input means receives a frame from the outside of the circuit and outputs it to the corresponding output route selection means. The output route selection means gives the frame input from the frame input means. The frame output route is determined based on the information set and / or the attributes set in advance in the connection, and the input The frame is output to the frame input means corresponding to the frame input means through which the frame has passed and the frame output means of the determined output route, and the bandwidth control means stores the input frame and the connection information of the stored frame as the bandwidth. The allocation unit is notified, and the accumulated frame is read based on the read connection and the read timing notified from the band allocation unit, and the band allocation unit determines the allocation band to each connection based on the band distribution ratio set for each connection. Then, based on the connection information of the storage frame notified from each band control means and the allocated bandwidth to each connection, the read connection and the read timing are determined, and the read connection and the read timing are notified to each band control means, The frame output means is read by the corresponding band control means. The to-frame multiplexing, and transmits to the circuit outside.

According to another embodiment of the frame readout scheduling circuit of the present invention,
The band allocating unit includes a main band allocating unit and a sub band allocating unit corresponding to each band control unit, and the main band allocating unit stores the corresponding band control unit notified from each sub band allocating unit. Based on the connection information of the frame and the allocated bandwidth to each connection, determine the bandwidth control means and read timing that permit reading, and notify all sub-band allocation means of the bandwidth control means and read timing that allow the reading, The sub-band allocation unit selects one connection information based on the connection information of the storage frame of the corresponding band control unit and the allocated band to each connection and notifies the main band allocation unit of the connection information. When the read permission is notified from the main band allocating unit, the selected one connection is set as a read connection, and the main band allocating unit With al notified read timing, it is also preferable to notify the corresponding bandwidth control means.

According to another embodiment of the frame readout scheduling circuit of the present invention,
Traffic that passes through the frame output means is monitored, traffic monitoring means that notifies the output route bandwidth determination means of traffic information, and usable bandwidth is determined for each output route based on the traffic information notified from the traffic monitoring means. And an output route bandwidth determining means for notifying the bandwidth allocating means, wherein the bandwidth allocating means is an available bandwidth for each output route notified from the output route bandwidth determining means and a bandwidth set for each connection. It is also preferable to determine the bandwidth allocated to each connection based on the distribution ratio.

Furthermore, according to another embodiment of the frame readout scheduling circuit of the present invention,
The bandwidth control unit includes a frame distribution unit that distributes frames based on information given to an input frame and / or an attribute set in advance in a connection, and a frame storage that stores the allocated frames. And frame read-out for reading out the frame stored in each frame storage unit based on the read connection and the read timing notified from the band allocation unit It is also preferable to have a means.

  The fairness of the allocated bandwidth between the connections can be ensured while avoiding the limitation due to the memory access bandwidth, and the number of bandwidth control units through which the frame passes has not increased, so there is no increase in delay.

  By distributing the bandwidth allocation process, the scalability of the number of connections accommodated can be improved while maintaining the above effect.

  By monitoring the traffic and dynamically changing the usable bandwidth of the output route based on the traffic situation, there is an effect of preventing frame discard at the frame output unit and an effective bandwidth utilization rate. .

  The best mode for carrying out the present invention will be described in detail below with reference to the drawings.

  First Embodiment FIG. 3 is a functional block diagram of a first embodiment of a frame readout scheduling circuit according to the present invention. According to FIG. 3, the frame readout scheduling circuit includes a frame input unit 1, an output route selection unit 4, a band control unit 2, and a frame output unit 3. The band control unit 2 includes a frame distribution unit 21, a frame storage unit 22, and a frame reading unit 23. The frame input unit 1 is provided corresponding to the input route, and the frame output unit 3 is provided corresponding to the output route. The band control unit 2 is provided corresponding to the set of the frame input unit 1 and the frame output unit 3.

  The frame input unit 1 receives a frame input to the frame reading scheduling circuit from the outside of the circuit, and outputs the received frame to the output route selection unit 4.

  The output route selection unit 4 determines the output route of the frame based on the header information of the input frame and / or information preset in the connection, the frame input unit 1 that inputs the frame, and the determination To the bandwidth control unit 2 corresponding to the output route. The header information for determining the output route is the MAC address of the Ethernet (registered trademark) frame, the VLAN ID of the VLAN tag, or the like.

  The frame distribution unit 21 of the bandwidth control unit 2 distributes the frame for each user and for each class based on information given to the frame from the output route selection unit 4 and / or attributes set in advance in the connection. I do. By performing distribution for each user and for each class, it is possible to provide different service qualities for each connection. The frames distributed by the frame distribution unit 21 are stored in a frame storage unit 22 having a FIFO buffer.

  The frame reading unit 23 notifies the band allocation unit 5 of information about the connection of the frames stored in the frame storage unit 22, and the frames stored in the frame storage unit 22 are transmitted to the band allocation unit 5 as described later. Is read out based on the control from, and transmitted to the frame output unit 3. As a scheduling algorithm used by the bandwidth allocator 5, WFQ, WRR, or the like can be applied.

  The bandwidth allocation unit 5 links the bandwidth control units 2 in order to prevent the allocation bandwidth between connections accommodated in different bandwidth control units 2 from becoming unfair. It has a function to perform. Therefore, the bandwidth allocating unit 5 notifies the frame reading unit 23 of each band control unit 2 of the read connection and the read timing, and the frame read unit 23 of each band control unit 2 notifies at the read timing notified. The read connection frame is read from the frame storage unit 22 and output to the frame output unit 3.

  The frame output unit 3 is provided for each output route, and has a function of multiplexing frames received from the associated bandwidth control unit 2 and transmitting the multiplexed frame as an output of the frame readout scheduling circuit.

  FIG. 4 is a flowchart for explaining the operation of the bandwidth allocation unit 5. The bandwidth allocation unit 5 manages the queue status of the frame storage unit 23 of each bandwidth control unit 2 in an integrated manner, thereby linking the distributed bandwidth control units 2 and realizing fair bandwidth allocation between connections. It has the function to do.

  According to FIG. 4, first, information on an input frame is acquired (S41), and the queue status of each frame storage unit 23, that is, information on the connection to which the stored frame belongs is acquired (S42). Next, based on the information about the allocated bandwidth to each connection based on the preset allocated bandwidth ratio and the queue status, the bandwidth control unit 2 that performs reading, the connection that performs reading, and the read timing are determined (S43), The frame reading unit 23 of the bandwidth control unit 2 that performs reading is notified (S44). Receiving the notification, the frame reading unit 23 reads the frame of the notified connection from the frame storage unit 22 at the notified timing, and transmits it to the frame output unit 3 (S45). Thereafter, the above operation is repeated.

  Next, an allocated band will be described using an example in which switching is performed from two input ports of the apparatus, that is, two frame input units 1, to one output port, that is, one frame output unit. Each port has a physical bandwidth of 100 Mbit / s, and the first port accommodates a total of six connections: connections # 1 to # 3, and the second port includes connections # 4 to # 6. To do. The bandwidth ratio allocated to each connection is assumed to be connection # 1: # 2: # 3: # 4: # 5: # 6 = 3: 2: 2: 1: 1: 1. If there is sufficient traffic for all connections, the bandwidth allocated to each connection is: connection # 1: # 2: # 3: # 4: # 5: # 6 = 30M: 20M: 20M: 10M: 10M : 10M. In this case, the bandwidth control unit 2 accommodating connections # 1 to # 3 handles a total of 70 Mbit / s, and the bandwidth control unit 2 accommodating connections # 4 to # 6 processes a total of 30 Mbit / s. To do. Regardless of the bandwidth control unit 2 to be accommodated, fair bandwidth allocation is performed between connections transmitted to the same output route.

  When the input traffic of connections # 2, # 3, and # 6 is stopped, the bandwidth allocated to each connection is connection # 1: # 2: # 3: # 4: # 5: # 6 = 60M: 0M: 0M: 20M: 20M: 0M.

  According to this embodiment, it is possible to ensure the fairness of the allocated bandwidth between connections while avoiding the limitation due to the access bandwidth of the memory. Further, the fairness of the allocated bandwidth between connections is ensured without increasing the number of bandwidth control units 2 in the frame readout scheduling circuit, and there is no increase in delay because the number of passing bandwidth control units 2 is 1. .

  Second Embodiment This embodiment is characterized in that the bandwidth allocation process is distributed and scheduling is performed. FIG. 5 is a functional block diagram of a second embodiment of the frame readout scheduling circuit according to the present invention. According to FIG. 5, in place of the bandwidth allocation unit 5 of the first embodiment of FIG. 3, a main bandwidth allocation unit 6 and a sub-band allocation unit 7 corresponding to each bandwidth control unit 2 are provided.

  In the first embodiment, the bandwidth allocation unit 5 has determined the frame reading schedule in all the bandwidth control units 2, but in this embodiment, the sub-band allocation unit 7 corresponding to each bandwidth control unit 2 is the same. The bandwidth control unit performs frame read scheduling, and the main band allocation unit 6 performs adjustment between the sub-band allocation units 7, that is, the band control units.

The processing procedure in the present embodiment will be described by taking as an example the case of using WRR as a scheduling method.
(1) The main band allocating unit 6 creates a full-set WRR table to be used by the all frame reading unit 23 based on the guaranteed band ratio of the connections accommodated in the all band control unit 2.
(2) The sub-band allocation unit 7 corresponding to each band control unit 2 extracts a part related to the connection accommodated by the corresponding band control unit 2 from the full-set version WRR table created in (1), and generates a subset version. The WRR table is created.
(3) For each bandwidth control unit 2, the sub-band allocation unit 7 performs a WRR operation based on the created subset version WRR table, determines one connection to which the next readable frame belongs, and determines The main band allocation unit 6 is notified of the connection made.
(4) The main band allocating unit 6 determines a connection of a frame to be read next based on the full set version WRR table and the information notified from each sub band allocating unit 7, and notifies all the sub band allocating units 7. To do.
(5) Thereafter, (3) and (4) are repeated.

  The above process will be specifically described with reference to FIGS. FIG. 6 is a diagram showing an example of accommodation of connections, and FIG. 7 is an example of a WRR table corresponding to the accommodation example of FIG.

  According to FIG. 6, connections # 1 to # 3 are accommodated in the bandwidth control unit 2-1, connections # 4 to # 5 are accommodated in the bandwidth control unit 2-2, and connections to the bandwidth control unit 2-3. In which connections # 6 to # 8 are accommodated. The output paths of the connections # 1 to # 8 are the same. The guaranteed bandwidth ratio of the connections # 1 to # 8 is 4: 2: 2: 4: 4: 2: 1: 1.

  FIG. 7A is a full set version WRR table created by the main band allocating unit 6 when the connection shown in FIG. 6 is accommodated. 7B to 7D are subset version WRR tables created by the sub-band allocation units 7-1 to 7-3 corresponding to the band control units 2-1 to 2-3, respectively.

  The search operation of the WRR table in the main band allocating unit 6 and the sub band allocating units 7-1 to 7-3 is controlled to start the search from the same address in order to synchronize. The sub-band allocation units 7-1 to 7-3 notify the main band allocation unit 6 of one connection address that is closest to the current WRR table search position among the connections that have frames that can be transmitted. To do.

  In FIG. 7, when connections # 2, # 3, # 4, # 7, and # 8 have frames that can be transmitted and search starts from address 1 in the WRR table, subband allocation unit 7-1 , Address 5 (connection # 2), subband allocation unit 7-2 from address 3 (connection # 4), subband allocation unit 7-3 from address 12 (connection # 7), Each is notified to the main band allocation unit 6.

  The main band allocating unit 6 selects the nearest transmittable position in the WRR table search direction from among the addresses notified from each sub band allocating unit. In the above example, address 3 (connection # 4) is selected.

  The main band allocating unit 6 notifies each sub band allocating unit of a band control unit and an address that are permitted to be transmitted next. In the above example, the bandwidth controller 2-2 and the address 3 are notified. The bandwidth control unit permitted to send the frame sends the frame of the connection to be read (connection # 4).

  Subsequently, the main band allocating unit 6 searches for the next sendable position using the next address position of the address permitted to be sent as a search start position. Thereafter, the above operation is repeated.

  By applying this embodiment, there is an effect that the bandwidth allocation process can be distributed and the scalability of the number of connections accommodated can be improved.

  (Third embodiment) This embodiment is characterized in that the frame output unit 3 performs traffic monitoring and dynamically changes the usable bandwidth allocated to the output route based on the traffic situation. FIG. 8 is a functional block diagram of a third embodiment of the frame readout scheduling circuit according to the present invention. According to FIG. 8, in addition to the functional block diagram of the first embodiment of FIG. 3, a traffic monitoring unit 8 and an output route band determining unit 9 are provided.

  The traffic monitoring unit 8 monitors the status of traffic passing through the frame output unit 3 and notifies the output traffic band determining unit 9 of the monitored traffic information.

  The output route bandwidth determination unit 9 determines the usable bandwidth for each output route based on the traffic information notified from the traffic monitoring unit 8 and notifies the bandwidth allocation unit 5 of the usable bandwidth.

  By providing the bandwidth allocation unit 5 with feedback based on the traffic situation passing through the frame output unit 3, the frame output unit 3 is effectively incorporated with a link aggregate function and a fault tolerance function for switching to a protection line when a failure occurs. Is possible.

  FIG. 9 is a diagram for explaining the link aggregate function of the frame output unit 3. By connecting a plurality of transmission lines to the frame output unit 3 and distributing the traffic output from the frame output unit 3 to the respective transmission lines by the link aggregate unit 10 in the frame output unit 3, a plurality of transmission lines Can be regarded as one virtual transmission line.

  If the link aggregate unit 10 performs ideal load distribution, the transmission band of the virtual transmission line is the sum of the transmission bands of the respective transmission lines. However, when the load distribution of the link aggregate unit 10 is biased, the bandwidth usage rate decreases, and the bandwidth of the virtual transmission path becomes smaller than the total of the transmission paths.

  When the traffic monitoring unit 8 detects the decrease in the bandwidth usage rate and feeds back the bandwidth allocation unit 5, it is possible to prevent the frame output unit 3 from causing a frame discard. Conversely, when the link aggregate unit 10 realizes ideal load distribution, the bandwidth usage rate of the virtual transmission path can be improved by increasing the bandwidth allocated by the bandwidth allocation unit 5. Can do.

  Further, even when a failure occurs in one of the transmission lines constituting the virtual transmission line, it is only necessary to reduce the bandwidth allocated by the bandwidth allocating unit 5. State changes can be concealed. As a result, the fault tolerance function can be realized without complicating the configuration of the bandwidth controller 2. Furthermore, it is not necessary to change the setting of the bandwidth control unit 2 due to a failure, and the efficiency of network operation can be realized.

  By applying this embodiment, the allocated bandwidth can be increased / decreased in accordance with fluctuations in the available bandwidth, and there is an effect of preventing frame discard at the frame output unit 3 and an effective bandwidth utilization rate. .

It is a block diagram which shows the example of the frame reading scheduling circuit by a prior art. It is a block diagram which shows the other example of the frame reading scheduling circuit by a prior art. It is a functional block diagram of a first embodiment of a frame readout scheduling circuit according to the present invention. It is a flowchart for demonstrating operation | movement of a band allocation part. It is a functional block diagram of 2nd embodiment of the frame read scheduling circuit by this invention. It is a figure which shows the example of accommodation of a connection. It is an example of a WRR table in case the connection of FIG. 6 is accommodated. It is a functional block diagram of 3rd embodiment of the frame read scheduling circuit by this invention. It is a figure for demonstrating the link aggregate function of a frame output part.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Frame input part 2, 2-0, 2-1, 2-2, 2-3 Band control part 21 Frame distribution part 22 Frame storage part 23 Frame reading part 3 Frame output part 4 Output route selection part 5 Band allocation Unit 6 Main Band Allocation Unit 7, 7-1, 7-2, 7-3 Sub Band Allocation Unit 8 Traffic Monitoring Unit 9 Output Route Band Determining Unit 10 Link Aggregate Unit

Claims (4)

In a circuit that accommodates one or more connections and performs scheduling for frame reading,
A plurality of frame input means respectively corresponding to a plurality of input routes, a plurality of frame output means respectively corresponding to a plurality of output routes, and a plurality of output route selections provided corresponding to the plurality of frame input means, respectively. Means, a plurality of bandwidth control means provided corresponding to each combination of the plurality of frame input means and the plurality of frame output means, and a bandwidth allocation means,
The frame input means receives a frame from the outside of the circuit and outputs it to the corresponding output route selection means.
The output route selection means determines the output route of the frame based on the information given to the frame input from the frame input means and / or the attribute preset in the connection, and the input frame has passed Outputting a frame to the bandwidth control means corresponding to the frame input means and the frame output means of the determined output route;
The bandwidth control means accumulates the input frame, notifies the bandwidth allocation means of connection information of the accumulated frame, reads the accumulated frame based on the read connection and the read timing notified from the bandwidth assignment means,
The bandwidth allocating means determines the allocated bandwidth to each connection based on a bandwidth distribution ratio set for each connection, and based on the connection information of the stored frame notified from each bandwidth control means and the allocated bandwidth to each connection, Determining a read connection and a read timing, and notifying each band control means of the read connection and the read timing;
The frame output scheduling circuit multiplexes the frames read by the corresponding band control means and transmits them to the outside of the circuit. The band allocation means includes a main band allocation means and a sub-band allocation means corresponding to each band control means,
The main band allocating unit determines the band control unit and the read timing for permitting reading based on the connection information of the stored frame of the corresponding band control unit and the allocated band to each connection notified from each sub band allocating unit. And notifying all the sub-band allocation means of the bandwidth control means and the read timing permitting the reading,
The sub-band allocation unit selects one connection information based on the connection information of the storage frame of the corresponding band control unit and the allocated band to each connection and notifies the main band allocation unit of the connection information. When the read permission is notified from the main band allocating unit, the selected one connection is set as a read connection, and the corresponding band control unit is notified together with the read timing notified from the main band allocating unit. The frame readout scheduling circuit according to claim 1. Traffic monitoring means for monitoring traffic passing through the frame output means and notifying the output route bandwidth determining means of traffic information;
Based on the traffic information notified from the traffic monitoring means, the usable bandwidth is determined for each output route, and the output route bandwidth determining means for notifying the bandwidth allocation means,
The band allocating unit determines an allocated band to each connection based on an available band for each output route notified from the output route band determining unit and a band distribution ratio set for each connection. The frame readout scheduling circuit according to claim 1 or 2. The band control means includes
Frame distribution means for distributing frames based on information assigned to the input frame and / or attributes set in advance in the connection;
Frame storage means for storing the sorted frames, respectively.
Frame readout means for notifying the bandwidth allocation means of connection information of the frames stored in the frame storage means, and for reading out the frames stored in each frame storage means based on the readout connection and readout timing notified from the bandwidth allocation means. The frame readout scheduling circuit according to claim 1, wherein the frame readout scheduling circuit is provided.

Images