JP4135007B2 - ATM cell transfer device - Google Patents

Description

  The present invention relates to a packet relay device connected to a packet transfer network, and more particularly to a traffic shaping device in a packet relay device.

  In packet transfer in a network such as the Internet, a user divides an information sequence into a data string (payload) having a length of several tens to several tens of thousands of bytes, and destination information and control according to a format determined for each communication protocol. Information is transferred using a packet to which information (header) is added. The packet length differs for each protocol, and there is a variable length for each packet such as IP (Internet Protocol) and a fixed length such as ATM (Asynchronous Transfer Mode).

In recent years, inexpensive services have been applied to public packet networks, and virtual private networks (VPNs) in which a plurality of private networks are connected via public packet networks have attracted attention. FIG. 2 shows a connection diagram of a corporate network through a public network. In FIG. 2, a private network A 41 and a private network B 42 are connected via a public network 40. In general, when communicating via a public network, a user makes a contract with a public network administrator regarding the transmission bandwidth and priority of packet transfer before packet transfer. When a contract between the user and the public network manager is established and the terminal starts to transfer packets toward the public network, the relay band 402 located at the entrance of the public network monitors the transmission band of the terminal, and the contract contents Decrease the priority of the packet of the terminal that violates or discard the violating packet. This monitoring function on the public network side is called UPC (Usage Parameter Control). Even if a packet is discarded during communication, the receiving terminal normally recognizes that the packet has been discarded, and a packet retransmission request is issued to the transmitting terminal, and the transmitting terminal has a function to retransmit the packet. Although there is no final loss of information, it is desirable that packet discard does not occur because the transfer delay becomes very large and the network is congested by the retransmitted packets. Therefore, it is necessary for the relay apparatus 401 that transmits a packet toward the public network to control the transmission band and transmit the packet so that the packet is not discarded by the UPC of the public network. This function of controlling the packet transmission band is called a traffic shaping function or simply a shaping function. In addition to the relay device directly connected to the public network as described above, the shaping device for realizing the shaping function is a user's transmission terminal or an exit of the public network that transmits packets toward the private network. It may be necessary for the part.

The service provided by the public network to the user, that is, the contract between the user and the public network administrator is to secure a certain bandwidth within the public network and then forward the packet, and to secure the bandwidth within the public network ATM. It is roughly classified into a best-effort contract that forwards packets without using a network. The former is suitable for transferring voice and the like because it can always transfer packets in a fixed band without being affected by the traffic volume of other users in the public network. In the latter case, depending on the traffic volume of other users, the transfer delay may increase or the packet may be discarded in the network. However, the latter is generally cheaper than the fixed bandwidth contract, and FTP (File Transfer Protocol) or It is used for transferring bursty (sudden) data traffic such as electronic mail. Recently, a class that guarantees a certain bandwidth even when the public network is congested despite a best effort contract has been proposed (referred to as GFR (Guaranteed Frame Rate) in ATM). In this class, the minimum guaranteed bandwidth and the maximum transfer bandwidth are contracted before packet transfer, packets are transferred at the maximum transfer bandwidth when the public network is not congested, and the minimum guaranteed bandwidth is always guaranteed even when the network is congested. Transferred.

A method for realizing a shaping device is described in, for example, Japanese Patent Application Laid-Open No. 9-307566 “Traffic Shaping Device” (Prior Art 1). Prior art 1 is described with respect to ATM. In the prior art 1, a queue is provided for each contract unit (for example, VC (Virtual Connection)) to be shaped, and the VC of the VC transmitted at the time of transmitting a cell (generally, a fixed-length packet used in ATM is particularly referred to as “cell”). A time at which the next cell can be transmitted (hereinafter, “scheduled transmission time”) is calculated and stored using a binary tree structure. That is, at the bottom of the binary tree, the scheduled transmission time of each VC is stored, the VC of the time when the scheduled transmission time is early (the one that is in the past in time) wins up, and finally the scheduled transmission time is the most. An early VC is selected. Therefore, a VC transmission scheduled time (one of the values at the bottom) to be transmitted with the highest priority is stored at the top of the binary tree. The calculation and sorting of the scheduled transmission time is performed not only at the time of cell transmission, but also when a cell is received without a transmission waiting cell. Thus, since sorting can be performed using the sorting result (binary tree structure) at the previous cell transmission, a VC to be transmitted with the highest priority can be selected in the processing time of the order of log (number of VCs). .

  Usually, in packets transmitted on a communication path, important packets and less important packets are mixed. Here, an important packet is a traffic packet that requires low-latency transfer such as telnet, and a less important packet is a traffic packet that has little influence even when the delay is large, such as e-mail. That is. In the case where important packets and less important packets are mixed, it is important to perform priority control in which important packets are preferentially transmitted even when the network is congested. Therefore, a field indicating the priority of the packet is prepared in the header portion of the normal packet. For example, in the case of an IP packet, it is a service type (Type of Service) field, and in the case of an ATM cell, it is a CLP (Cell Loss Priority) bit. In the following, for the sake of simplicity, the priority will be described in two stages (high priority / low priority), but a finer priority can be given to IP packets. A packet assigned a high priority is described as a high priority packet, and a packet assigned a low priority is described as a low priority packet.

If a conventional shaping device is applied to a best-effort service that guarantees bandwidth, all packets are transmitted with high priority. The high priority packet exceeding the guaranteed bandwidth is lowered in priority by the UPC function. At this time, the high priority packet and the low priority packet are determined without considering the above important packet and non-important packet. Therefore, an important telnet may become a low-priority packet, or a less important Web packet may become a high-priority packet, which is not a priority assignment desirable for the user. Within a shaping device, it is easy to assign important packets to high-priority packets and non-important packets to low-priority packets, but do not perform shaping so that the transmission bandwidth of high-priority packets is below the guaranteed bandwidth. Then, since the priority is randomly lowered by UPC, this is also not a priority assignment desirable for the user. In addition, when the traffic amount of important packets is small, the guaranteed bandwidth cannot be obtained. However, since the main billing target is the guaranteed bandwidth, it is important to use up the guaranteed bandwidth effectively.

A first object of the present invention is to transmit a packet to be preferentially transmitted among packets transmitted to the same destination in a guaranteed bandwidth (contract before packet transfer), and if there is a margin in the communication channel bandwidth, priority is given. It is an object of the present invention to provide a shaping device that transmits a non-priority packet so that the total bandwidth of the packet transmission band and the non-priority packet transmission band is equal to or less than the maximum transfer band (contract before packet transfer).

A second object of the present invention is a shaping apparatus that performs priority allocation desirable for the above-mentioned user, and further uses a guaranteed bandwidth effectively by transmitting a part of a less important packet as a high priority packet. Is to provide.

A third object of the present invention is to provide a shaping device corresponding to a GFR service that guarantees a bandwidth in units of packets in an upper layer in an ATM network.

  In order to solve the first problem, in the present invention, a queue (hereinafter referred to as a priority queue) for storing high priority packets for each user, A queue for storing priority packets (hereinafter referred to as a non-priority queue) is provided. Each of the priority queue and the non-priority queue may be one, or a plurality of queues may exist.

In addition, the scheduled transmission time of the first packet of transmission waiting packets stored in the priority queue is calculated so as to protect the guaranteed bandwidth, and the scheduled transmission time of the first packet of transmission waiting packets stored in the non-priority queue is immediately A scheduled transmission time calculation circuit for calculating a transmission time and calculating a scheduled transmission time corresponding to a transmission band (maximum contract bandwidth) including the priority queue / non-priority queue is provided. Further, a priority information adding circuit is provided that gives a high priority to a packet read from the priority queue and gives a low priority to a packet read from the non-priority queue. With the scheduled transmission time calculation circuit and priority information addition circuit, important packets can be transmitted in the guaranteed bandwidth as high-priority packets, and non-important packets in the remaining bandwidth (maximum contract bandwidth-guaranteed bandwidth) with low priority It can be sent as a packet.

The scheduled transmission time calculation circuit refers to the queue length (number of accumulated packets) of the priority queue when calculating the scheduled transmission time of the priority queue, and if the packet exceeds a certain amount, the guaranteed bandwidth is calculated. The time that is transmitted immediately without observing may be calculated as the scheduled transmission time. As a result, the number of packets accumulated in the priority queue increases due to shaping, and the phenomenon of overflow from the queue can be avoided.

In order to solve the second problem, in the present invention, when there is no transmission waiting packet in the priority queue in the priority assigning circuit regardless of the time when the packet should be transmitted from the priority queue. A function of giving high priority to the read waiting packet in the non-priority queue is provided. As a result, even when the traffic amount of important packets is small, the guaranteed bandwidth can be transmitted as priority packets, and the guaranteed bandwidth can be used effectively.

In order to solve the third problem, in the present invention, the IP packet is transmitted only when an upper layer packet last cell (hereinafter referred to as an EOP (End Of Packet) cell) is detected and an EOP cell is transmitted / received. A function is provided for performing processing when data is transmitted and received. As a result, cells can be transmitted and received in units of higher layer packets, and shaping corresponding to the GFR service can be performed.

  As described above, according to the present invention, an important packet can be transmitted as a high priority packet in the guaranteed bandwidth, and if there is a free time between important packets, an unimportant packet is set as a low priority packet. A shaping apparatus that can transmit without gaps can be provided. Therefore, packets can be transferred at the maximum bandwidth when the network is free, important packets can be transferred at the guaranteed bandwidth even when the network is congested, and the bandwidth of the communication path can be used effectively. Can do. Furthermore, when the traffic amount of important packets is small, non-important packets can be transmitted as high priority packets, and the guaranteed bandwidth can be utilized to the maximum.

In addition, according to the present invention, it is possible to configure a shaping device for a GFR service that performs UPC in units of upper layer packets in ATM, and when the network is free, upper layer packets can be transferred with the maximum bandwidth. Even when the network is congested, priority packets in higher layers can be transferred in the guaranteed bandwidth.

  FIG. 3 shows a configuration diagram of a packet relay apparatus to which the present invention is applied. Hereinafter, the packet will be described as an IP packet. The format of the IP packet is shown in FIG. In FIG. 3, the packet relay apparatus 98 is connected to the networks 99-1 to 99-3. The packet relay device 98 includes line-corresponding units 2-1 to 2-3 corresponding to types of connected lines (such as Ethernet, ATM, and frame relay), and packet processing units 3-1 to 3-1 that determine the next transfer destination. 3-2, and a crossbar switch 8 that relays a plurality of packet processing units. In FIG. 3, a plurality of line corresponding units 2-1 and 2-2 are connected to one packet processing unit 3-1, by a bus 9, but one line corresponding unit is connected to one packet processing unit. It may be configured. In FIG. 3, a plurality of packet processing units 3-1 and 3-2 are connected by the crossbar switch 8. However, the configuration may be such that there is only one packet processing unit. In this case, the crossbar switch 8 is unnecessary. is there.

Next, an operation in which the packet relay device 98 receives a packet, searches for a transmission destination, and transmits the packet toward the search result line will be described. The packet received from the private network 99-2 is sent to the packet transfer unit 4 in the packet processing unit 3-1, via the line corresponding unit 2-2 and the bus 9. The packet transfer unit 4 temporarily stores the received packet in the packet buffer 5 and uses a route search unit for a header in which information necessary for routing such as a transfer destination IP address (Destination IP Address in FIG. 4) is written. 6 is notified. The route search unit 6 reads the routing destination stored in the routing information memory 7 from the transfer destination address in the header. The route search unit 6 notifies the packet transfer unit 4 of the routing destination information as a result of reading. The packet transfer unit 4 reads the packet from the packet buffer 5 and transfers the read packet to the routing destination notified from the route search unit 6. Depending on the search result of the routing destination, the packet may be transferred to the line corresponding unit via the crossbar switch 8, another packet processing unit, or the bus, or may be transferred directly to the line corresponding unit via the bus 9. For example, when transferring to the public network 99-1, the packet is transferred to the line corresponding unit 2-1 via the bus 9, and the packet is sent by the shaping device 1 to protect the contract bandwidth with the public network 99-1. It is shaped and transmitted to the public network 99-1 via the physical layer corresponding unit 111 (in the case of transmission toward a private network, generally, shaping is not necessary).

FIG. 1 is a block diagram of the shaping device 1 in the line corresponding unit 2-1. In FIG. 1, a shaping apparatus 1 includes a packet buffer unit 10 for temporarily queuing a packet, a priority of a received packet, and a queuing destination determination circuit that determines a queue in which the received packet should be queued. 11. Store from the scheduled transmission time for each queue to the scheduled transmission time of the queue to be transmitted with the highest priority for each user using a binary tree structure, and further transmit with the highest priority from the scheduled transmission time for each user The scheduled transmission time storage circuit 12 that stores the user's scheduled transmission time using the binary tree structure, and the binary tree structure transmission scheduled time stored in the transmission scheduled time storage circuit 12 has the highest priority. A sorting circuit 17 that selects a queue to be transmitted and writes the result back to the scheduled transmission time storage circuit 12; According to the scheduled transmission time calculation circuit 13 that stores the estimated transmission time of the calculation result in the scheduled transmission time storage circuit 12 and the scheduled transmission time for each queue stored in the scheduled transmission time storage circuit 12. A packet reading circuit 14 for reading and transmitting packets from, a priority information giving circuit 15 for giving priority information (high priority / low priority) to the transmitted packets, and a clock indicating the current time 16.

The packet buffer 10 is a priority queue 100 for queuing priority packets to be transmitted within the guaranteed bandwidth (it exists for each user. In FIG. 1, the priority queue for the user 1 is 100-1, the priority queue for the user 2 is 100- 2), a non-priority queue 101 that queues non-priority packets to be transmitted when the network is free outside the guaranteed bandwidth (in FIG. -2).

The scheduled transmission time calculation circuit 13 keeps the transmission interval so as not to exceed the guaranteed bandwidth, and the immediate delivery time calculation circuit 130 that calculates the scheduled transmission time 1300 for transmitting the packet immediately from the packet reception time or the packet transmission time. Which of the two scheduled transmission times 1300 and 1310 is written in the bandwidth-guaranteed read time calculation circuit 131 for calculating the scheduled transmission time 1310 and the scheduled transmission time storage circuit 12, or neither of them is written , And a maximum bandwidth reading circuit 133 for calculating a scheduled transmission time for keeping a transmission interval that does not exceed the maximum contract bandwidth. Specifically, the immediate delivery time calculation circuit 130 uses the current time 1600 notified by the clock 16 to calculate the scheduled transmission time 1300,
Scheduled transmission time 1300 = current time + 1
Calculate as That is, if there is no packet to be transmitted from another queue, the packet is transmitted immediately. Further, in the band guarantee read time calculation circuit 131 and the maximum band read time calculation circuit 133, an algorithm that allows transmission on the contract band as an average even when fluctuations occur due to competition of transmission times of a plurality of VCs. To calculate the scheduled transmission time 1310. For example, if the leaky bucket algorithm described in “The ATM Forum TM 4.0” or the like is used, it is possible to absorb the fluctuation as described above and transmit a packet with a contract bandwidth as an average.

Next, a storage format of the scheduled transmission time storage circuit 12 is shown in FIG. 6, and a detailed block diagram is shown in FIG. As shown in FIG. 6, the scheduled transmission time storage circuit 12 stores a scheduled transmission time 30 for each queue, a time valid flag 31 indicating that the scheduled transmission time 30 is valid, and a packet waiting for transmission in the queue. A packet valid flag 32 indicating that the packet is valid is stored. As shown in FIG. 7, the scheduled transmission time storage circuit 12 includes a memory 122 that stores information related to the scheduled transmission time, and a memory control circuit that generates a control signal for the memory 122 and sends read data from the memory 122 to each block. 120 and a time valid flag update circuit 121 that determines whether or not the scheduled transmission time 30 stored in the memory 122 is a valid value and updates the time valid flag 31.

Here, the meaning of the time valid flag will be described. The clock 16 that determines the shaping time is normally configured as a counter having a finite number of bits, but in this case, the same time is indicated for every fixed period determined by the number of bits of the counter. In other words, even if a certain scheduled transmission time is stored in the memory 122, the counter indicates that the scheduled transmission time is correct, or the counter has turned more than one round (in the past). It cannot be determined whether the time is indicated. This is distinguished by the time valid flag 31. The time valid flag 31 is a flag that becomes ‘1’ when the scheduled transmission time 30 indicates the correct time, and becomes ‘0’ when the counter indicates an illegal time that has been rotated one or more times.

The operation until the packet received from the packet transfer unit 4 via the bus 9 is transmitted to the line using the shaping apparatus 1 having the above-described configuration will be described.

The sorting circuit 17 performs the same sorting as the sorting method shown in the prior art 1.

(1) Packet Receiving Operation The packet receiving operation here indicates an operation when the shaping apparatus 1 receives a packet from the packet transfer unit 4 via the bus 9. When the shaping apparatus 1 receives a packet, first, the queuing destination discriminating circuit 11 determines whether to queue the received cell in the priority queue 100 or the non-priority queue 101. For example, in the case of an IP packet, the queue is determined by information such as service type, packet length, protocol type, SIP (Source IP Address), DIP (Destination IP Address), etc. in the header of the received packet (shaded in FIG. 4). This is performed using the field information indicated by. When the queuing destination queue is determined, the received packet is queued in the packet buffer 10. Simultaneously with the queuing, a signal 1100 indicating which queue is queued is sent to the scheduled transmission time calculation circuit 13. The scheduled transmission time calculation circuit 13 reads the scheduled transmission time 30, the time valid flag 31, and the packet valid flag 32 regarding the queue in which the received packet stored in the scheduled transmission time storage circuit 12 is queued.

An operation rule of the selection circuit 132 in the scheduled transmission time calculation circuit 13 is shown in FIG. 5, and a flowchart at the time of reception is shown in FIG. When the packet valid flag = 1 (step 50 in FIG. 9), it means that one or more packets have already been queued and the scheduled transmission time for the first transmission waiting packet has been calculated. The scheduled time is not updated. When the packet valid flag = 0 and the time valid flag = 0 (step 51 in FIG. 9), the received packet is queued in an empty queue, and the stored transmission scheduled time is sufficiently long. Therefore, it is necessary to update the scheduled transmission time because it is invalid. When the packet valid flag = 0 and the time valid flag = 1, the stored transmission scheduled time is a valid time. If the stored scheduled transmission time is in the future compared with the current time (step 52 in FIG. 9), the scheduled transmission time must not be updated to prevent the shaping interval from being narrowed, but it is stored. If the scheduled transmission time is the same as the current time or in the past compared to the current time, there is already an interval longer than the shaping interval, so the shaping interval can be maintained even if it is immediately issued. Update the scheduled transmission time. Since the update of the scheduled transmission time at the time of packet reception is all for prompt delivery, the scheduled transmission time 1300 calculated by the immediate delivery time calculation circuit 130 is always used when updating the scheduled transmission time. The scheduled transmission time area 30 of the storage circuit 12 is overwritten (step 53 in FIG. 9). Since the corresponding queue has received a packet, the packet valid flag 32 is always set to 1.
Furthermore, the scheduled transmission time for each user is changed according to the same rule.

As described above, the scheduled transmission time storage circuit 12 also stores the scheduled transmission time of the queue that should be transmitted with the highest priority. However, because the scheduled transmission time 30 and the packet valid flag 32 are updated by packet reception, The queue to be transmitted with the highest priority may have changed. Therefore, sorting is performed by the sorting circuit 17 based on the updated information, and the queue to be transmitted with the highest priority is selected again.

(2) Packet transmission operation The packet transmission operation here refers to an operation of transmitting a packet from the shaping apparatus 1 toward the line. Packet transmission is performed asynchronously with packet reception. In FIG. 1, the packet reading circuit 14 reads the scheduled transmission time 30, the time valid flag 31, and the packet valid flag 32 of the user who should be transmitted with the highest priority stored in the scheduled transmission time storage circuit 12. The user is determined to be able to transmit only when the packet valid flag 32 = 1, the time valid flag 31 = 1, and the scheduled transmission time 30 ≦ current time (the scheduled transmission time 30 is past or present). . In other cases, even packets in the queue that should be transmitted with the highest priority cannot be transmitted, and therefore, packets in all queues cannot be transmitted. When a user packet to be transmitted with the highest priority is transmitted, the scheduled transmission time 30, the time valid flag 31, and the packet valid flag 32 of the user to be transmitted with the highest priority among the users are read. The packet is read only when the packet valid flag 32 = 1, the time valid flag 31 = 1, and the scheduled transmission time 30 ≦ the current time (the scheduled transmission time 30 is past or present). Otherwise, therefore, no packet is sent from any queue. When both the priority queue and the non-priority queue of the same user are in a readable state, the priority queue packet is always transmitted (full priority control).

The packet read from the packet buffer 10 by the packet reading circuit 14 is transferred to the priority information adding circuit 15 and given priority information. The priority information is a service type field (Type of Service in FIG. 4) in the case of an IP packet, and indicates a CLP bit in the case of an ATM cell. The priority information assigning circuit 15 assigns a high priority to a packet read from the priority queue 100 and a low priority to a packet read from the non-priority queue 101, and transmits the packet to the line.

When a packet is transmitted, the scheduled transmission time 30 is updated for the next packet queued in the same queue. A signal 1400 indicating the type of queue transmitted at the time of packet transmission is sent to the scheduled transmission time calculation circuit 13. An operation rule of the selection circuit 132 in the scheduled transmission time calculation circuit 13 is shown in FIG. 5, and a flow chart at the time of transmission is shown in FIG. If the transmitted packet is a packet read from the priority queue, the calculation result 1310 of the band guaranteed read time calculation circuit 131 is selected to protect the guaranteed band (step 54-1 in FIG. 10). When a packet in the non-priority queue is transmitted, it is only necessary to immediately issue a packet, so that the calculation result 1300 of the immediate delivery time calculation circuit 130 is selected (step 54-2 in FIG. 10). The selected scheduled transmission time is overwritten in the scheduled transmission time area 30 of the scheduled transmission time storage circuit 12. At the same time, the scheduled transmission time for each user is also updated and overwritten.

Further, when the queue from which the packet is read out becomes empty due to the transmission of the packet (queue length = 0), the packet valid flag = 0 is stored in the scheduled transmission time storage circuit 12. If the queue is not emptied even when a packet is transmitted (queue length> 0), the packet valid flag 32 of the scheduled transmission time storage circuit 12 is not updated (packet valid flag = 1). The time valid flag is not updated from the state “1”.

(3) Time Valid Flag Update Operation In the present invention, a timepiece having a structure as shown in FIG. 8 is used. A certain value (time) of the clock 89 having a finite number of bits is the current time 80, and is counted up at a constant speed (moving clockwise). The count-up speed depends on the bandwidth of the transmission destination line. The area where the current time 80 has already passed is the past area 81, and the area where the current time 80 has not yet reached is the future area 82. An uncertain area 83 is provided at the point of contact between the past area 81 and the future area 82 that is not the current time 80. The uncertain area 83 is an area that is neither the past nor the future, and is always at a certain distance (time difference) from the current time.

If the uncertain area 83 is not provided, the transmission scheduled time that was in the past at a certain time becomes a future time just by advancing the time by one, and correct shaping cannot be performed. Arise. Therefore, when the scheduled transmission time 30 stored in the memory 122 is not updated and becomes the time of the past area 81, and further advances to the time of the indeterminate area 83, the time valid flag is set to “0”. .

The operation of the time valid flag update circuit 121 in the scheduled transmission time storage circuit 12 will be described with reference to the flowchart of FIG. The time valid flag update circuit 121 first reads the scheduled transmission time 30, queue time valid flag 31, and packet valid flag 32 for each queue from the memory 122 (step 55 in FIG. 11). When the read time valid flag 31 = 0, it is already determined that the scheduled transmission time 30 is invalid, so that all information is not updated (step 56 in FIG. 11). If the time valid flag 31 = 1 and the scheduled transmission time 30 is not in the indeterminate area 93, the scheduled transmission time 30 is still valid, and in this case as well, all information is not updated (step 57 in FIG. 11).
When the time valid flag 31 = 1, the scheduled transmission time 30 is in the indeterminate area 93, and the packet valid flag 32 = 1, there are still packets waiting to be transmitted, so the time valid flag must not be set to zero. Therefore, in this case, the scheduled transmission time is updated and written back to the time (94 in FIG. 9) farthest from the current time in the past area, and both the time valid flag and the packet valid flag remain at 1 without being updated. (Steps 58-1 and 59 in FIG. 11). When the time valid flag 31 = 1, the scheduled transmission time 30 is in the indeterminate area 93, and the packet valid flag 32 = 0, there is no packet waiting for transmission, so the scheduled transmission time and the packet valid flag are updated. The time valid flag is updated to 0 and written back to the memory 122 (steps 58-2 and 59 in FIG. 11).

Next, time update timing will be described. If a certain queue has not been updated even once in the indeterminate area 93, the scheduled transmission time enters the future area with the time valid flag = 1, so that the indeterminate area 83 is not provided. Correct shaping cannot be performed. For the above reasons, it is necessary to perform the above-mentioned time validity flag update operation once or more for all the queues in the indeterminate area. This can be easily realized by updating the scheduled transmission time at a period equal to or less than the time width of the uncertain area.

Although FIG. 1 shows an example in which one priority queue 100 and one non-priority queue 101 exist for each user, each user has a plurality of priority queues and a plurality of non-priority queues. Also good. If the number of queues increases, finer priority control can be performed, for example, the user A's email is transferred in preference to the user B's email even in the same email traffic. When there are a plurality of priority queues, the parameters of the leaky bucket algorithm must be set so that the guaranteed bandwidth is the sum of the transmission bandwidths of the plurality of priority queues. In addition, when there are a plurality of non-priority queues, priority control between the non-priority queues is complete priority control in which priority is given whenever there is a packet in the upper queue, or a set ratio (for example, 2: 1). In this case, weighted round robin (Weighted Round Robin) that transmits packets in the upper queue and the lower queue can be used.

In the embodiment of the shaping apparatus described above, since priority packets are shaped with the minimum guaranteed bandwidth, if the input bandwidth is larger, the queue may overflow and the packets may be discarded. In order to prevent this, when the queue is likely to overflow, a function of transmitting packets to the maximum without observing the minimum guaranteed bandwidth may be added. In the shaping apparatus shown in FIG. 1, when a priority packet is transmitted, the calculation result of the bandwidth guarantee read time calculation circuit 131 is set as the scheduled transmission time of the next packet. At this time, referring to the queue length of the priority queue, By correcting the selection condition based on the queue length, the above function can be easily realized. That is, when the queue length of the priority queue is smaller than a preset threshold, the calculation result of the bandwidth guaranteed read time calculation circuit 131 is set as the scheduled transmission time of the next packet as usual, and the queue length of the priority queue is set. However, when the value is larger than the threshold, it is only necessary to modify the condition of the selection circuit 132 so that the calculation result of the immediate extraction time calculation circuit 130 becomes the scheduled transmission time of the next packet. If the priority information for the bandwidth exceeding the guaranteed bandwidth is transmitted at a low priority, it is not discarded by the UPC on the network side.

In addition, if the input bandwidth of the priority packet is small, the transmission bandwidth of the packet transmitted with high priority will be lower than the guaranteed bandwidth, and the guaranteed bandwidth that is often the main target of charging cannot be used effectively. . In this case, if there is no packet waiting for transmission in the priority queue even when the scheduled transmission time of the priority queue is reached, the packet reading circuit 14 reads the packet from the non-priority queue, and the priority information adding circuit 15 has a high priority. The guaranteed bandwidth can be effectively used by adding a function for providing

FIG. 12 shows the state of a packet transmitted from the packet relay apparatus 98 including the shaping unit 1 described above toward the public network 99-1. The upper half of FIG. 12 shows the time interval of transmitted packets, and the horizontal axis is the time axis. The lower half shows the change in the transmission band at each time. Each user always transmits a packet in a band between the minimum guaranteed band and the maximum contracted band (area 1). At the same time, the number of users who transmit packets increases, and even if the transmission bandwidth is reduced, it does not fall below the minimum guaranteed bandwidth (area 2). If the number of users who transmit packets simultaneously decreases, the transmission bandwidth can be increased to the maximum contract bandwidth (area 3). In either case, high-priority packets do not depend on the number of other users sending them, and packets can always be sent in a fixed bandwidth, while low-priority packets have room in the communication channel bandwidth Only in that free band.

As a second embodiment, a GFR shaping apparatus using ATM cells will be described. FIG. 13 shows a block diagram of the GFR shaping apparatus. An ATM cell is a 53-byte fixed-length packet, and one or more cells gather to form an upper layer packet. However, when different packets in the same VC are mixed, the receiving terminal cannot identify the packet delimiter. Therefore, the cell reading circuit 74 has a function of continuously reading and transmitting cells of the same upper packet. Further, the queuing destination discriminating circuit 71 determines a queue for queuing the received cell with reference to the VPI, VCI, and CLP in the header of the received ATM cell. The last cell of the upper packet can be identified by the payload type (3 bits) in the cell header. When the payload type is “000” or “010”, it is the first / intermediate cell, and when it is “001” or “011”, it is the last cell. The other values indicate that the cell is a management cell (OAM cell / RM cell).

The following points are different from the IP packet transmission / reception operation. When an ATM upper layer packet is received, first, the SAR (Segmentation And Reassembly) 78 divides the packet into 48 bytes and adds an ATM header of 5 bytes to form an ATM cell. The ATM cell is a queuing destination discriminating circuit. 71. When the queuing destination discriminating circuit 71 receives the head / intermediate cell of the upper packet, it does not update the scheduled transmission time, the time valid flag, and the packet valid flag, but only when the last cell of the upper packet is received. The scheduled transmission time, time validity flag, and packet validity flag are updated. The process at the time of receiving the final cell is the same as the IP packet rule (see FIG. 14).

Next, the difference at the time of cell transmission is shown. Since the bandwidth guarantee must be performed for the upper packet, as described above, when the head / intermediate cell of the upper packet is transmitted, the cells need to be read continuously . Hand, when transmitting the last cell of the upper packet, selects the scheduled transmission time in the same rules as upon IP packet transmission (see Fig. 14).

As described above, the GFR shaping device can be easily obtained by simply adding the conditions of the last cell and the head / intermediate cell to the conditions of the selection circuit in the scheduled transmission time calculation circuit of the IP packet shaping device 1 of the present invention. Can be configured.

It is a block diagram which shows the structure of one Example of the traffic shaping apparatus to which this invention is applied. It is a connection diagram of a corporate network through a public network. It is a block diagram which shows the structure of one Example of a packet relay apparatus. It is a figure which shows the format of an IP packet. 6 is a table showing a selection rule of the selection circuit 132 in the scheduled transmission time calculation circuit 13. 3 is a diagram showing a storage format of a memory 122 in a scheduled transmission time storage circuit 12. FIG. 3 is a detailed block diagram of a scheduled transmission time storage circuit 12. FIG. It is a conceptual diagram of the shaping timepiece comprised using the counter of finite bit number. It is a flowchart for deciding the transmission scheduled time at the time of packet reception. It is a flowchart for deciding the transmission scheduled time at the time of packet transmission. It is a flowchart for time priority flag update. It is the conceptual diagram which showed the example of the transmission band of the shaping apparatus 1, and the packet transmitted. It is a block diagram which shows the structure of one Example of the traffic shaping apparatus for GFR to which this invention is applied. 10 is a table showing a selection rule of the selection circuit 732 in the scheduled transmission time calculation circuit 73.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1,7 ... Shaping apparatus, 10 ... Packet buffer, 100, 700 ... Priority queue, 101,701 ... Non-priority queue, 11, 71 ... Queuing destination discriminating circuit, 12, 72 ... Transmission scheduled time storage circuit, 13, 73 ... scheduled transmission time calculation circuit, 14 ... packet read circuit, 15, 75 ... priority information addition circuit, 16 ... clock, 17, 77 ... sorting circuit, 70 ... cell buffer, 74 ... cell read circuit, 78 ... SAR.

Claims (11)

An ATM cell transfer apparatus that is connected to an ATM network and includes a line corresponding unit corresponding to the type of the connected line,
In the line correspondence section,
A queue in which received ATM cells are stored;
Means for detecting an upper packet delimiter based on information in the header of the received ATM cell;
A scheduled transmission time calculation circuit for calculating a scheduled transmission time when the ATM cell in which a break of the upper packet is detected is received ;
In accordance with the scheduled transmission time, in the same queue as the queue delimit the upper packet is accumulated in the detected ATM cells, and ATM cell and the ATM cell compartment cutting is accumulated in the next detected ATM cell the ATM cell Le belonging to the same upper packet ATM cell transfer apparatus having a transmitter for transmitting the read circuit and the read ATM cell to be read from the queue. An ATM cell transfer apparatus according to claim 1, wherein
The ATM cell transfer apparatus, wherein the line corresponding unit further comprises a priority information adding circuit for writing information on priority in a header of the ATM cell read from the queue. An ATM cell transfer apparatus according to claim 2, wherein
The queue is
A priority queue in which ATM cells to which a guaranteed transmission bandwidth is assigned are stored;
A non-priority queue in which ATM cells to which no guaranteed transmission bandwidth is assigned are stored;
The line corresponding part further
Priority is determined by referring to information on at least one of VPI, VCI and priority described in the received ATM cell, and queuing to either the priority queue or the non-priority queue A queuing destination discriminating circuit to perform,
An ATM cell transfer apparatus comprising: a sorting circuit that refers to the scheduled transmission time and selects a queue to be transmitted with the highest priority. An ATM cell transfer apparatus according to claim 3, wherein
There are a plurality of priority queues for the same user , priority is set between the plurality of priority queues, and ATM cells are read from the queue with the highest priority among the queues having ATM cells waiting for transmission. An ATM cell transfer apparatus characterized by the above. An ATM cell transfer apparatus according to claim 3, wherein
A plurality of non-priority queues exist for the same user , priority is set between the plurality of non-priority queues, and ATM cells from the highest priority queue among the queues in which ATM cells waiting to be transmitted exist Is read and transmitted. An ATM cell transfer apparatus according to claim 3, wherein
The scheduled transmission time calculation circuit includes a circuit for calculating a scheduled transmission time for continuously reading ATM cells, and a circuit for calculating a scheduled transmission time for protecting the guaranteed transmission band, and further includes two calculation results as the scheduled transmission time. An ATM cell transfer apparatus comprising a selection circuit for selecting any one of the above. An ATM cell transfer apparatus according to claim 6 , wherein
When the line corresponding unit transmits an ATM cell from the priority queue, it selects a calculation result of a circuit for calculating a scheduled transmission time to protect the transmission guaranteed band, and the line corresponding unit transmits an ATM cell from the non-priority queue. An ATM cell transfer apparatus comprising a function of selecting a calculation result of a circuit for calculating a scheduled transmission time for continuously reading the ATM cells. An ATM cell transfer apparatus according to claim 6 , wherein
A threshold value is set in advance in the priority queue, and when the number of ATM cells stored in the priority queue does not exceed the threshold value, the selection circuit calculates a scheduled transmission time to protect the transmission guaranteed bandwidth. When the calculation result of the circuit is selected and the number of ATM cells stored in the queue exceeds the threshold, the calculation of the circuit that calculates the scheduled transmission time when the selection circuit continuously reads the packets An ATM is selected, and when the line corresponding unit transmits an ATM cell from the non-priority queue, a calculation result of a circuit for calculating a scheduled transmission time for continuously reading the ATM cell is selected. Cell transfer device. An ATM cell transfer apparatus according to claim 3, wherein
When the ATM cell reading circuit reads an ATM cell from the priority queue, the priority information adding circuit writes the priority information indicating high priority in the header portion of the ATM cell that has been read, and the ATM cell reading circuit When the ATM cell is read from the non-priority queue, priority information indicating low priority is written in the header portion of the read ATM cell. An ATM cell transfer apparatus according to claim 3, wherein
Priority information indicating a high priority in the header portion of the ATM cell read from the non-priority queue when the priority information adding circuit has no ATM cell waiting for transmission in the priority queue at the scheduled transmission time for the priority queue An ATM cell transfer apparatus characterized by writing and transmitting. An ATM cell transfer device according to claim 9 , wherein
An ATM cell transfer apparatus characterized in that, as the priority information, a value of a CLP bit in an ATM cell header is changed.

Images