Title of Invention

A FRAME DISCARD MECHANISM FOR PACKET SWITCHES

Abstract

The invention relates to a frame discard method for a packet switch and to a packet switch. The method comprises the steps of (a) receiving pack¬ets belonging to at least one transmission connection consecutive packets of an individual transmission connection forming frames, (b) switching packets from N input ports of the switch to N output ports of the switch, through at least one Intermediate port, and (c) discarding complete frames, if the load level in the switch exceeds a predetermined threshold. In order to combine a good frame level performance with implementation simplicity, the packets are dis¬carded in a switch where the maximum number of packets that can be trans¬mitted simultaneously to one port is smaller than N, In such a way that (i) when the number of packets simultaneously contending for an individual port ex¬ceeds said maximum number, at least one first packet of a frame is chosen to be discarded from among said packets, and (it) once a first packet of a frame has been discarded, the remaining packets of the same frame are discarded, regardless of the current buffering capacity of the switch. (Figure 5)

Full Text

Field of the invention This invention relates generally to a packet discard mechanism for packet switches. More particularly, the invention relates to a packet discard mechanism which discards whole frames instead of randomly discarding indi¬vidual packets (or cells). In a packet switched network most of the higher level data units to be delivered through the switches of the network are too large to be trans¬ferred in a single packet and must therefore be segmented for delivery. In this context, these higher level data units, which are used in various kinds of appli¬cations, are called frames. Figure 1 illustrates the relationship between pack¬ets and frames as used in this context; a transmission frame consists of M consecutive packets, each having a fixed length. In a TCP/IP over ATM net¬work, for example, a frame corresponds to an IP datagram and the packets correspond to ATM cells. The frame size (the number of packets in a frame) depends on the type of application using a transmission connection. If one or more of the packets of a frame are missing at the destina¬tion, the frame cannot be reassembled and must be discarded. Therefore, if the performance of the network is evaluated from the point of view of the ap¬plications sending and receiving these higher level data units, it should be clear that the end-to-end delay and the loss rate of these data units (i.e. frames) are more relevant performance indicators than the end-to-end delay and the loss rate of individual data packets. When random packet dropping policies are used in the network, it is more likely that the dropped packets belong to different frames than to the same frame. Therefore, the packet loss rate of such drop mechanisms cannot be an indication of the quality of service (QoS) on the application level. To eliminate this drawback, more sophisticated loss mechanisms have been proposed. One is what is called the early packet discard (EPD) scheme, which discards whole frames instead of randomly discarding packets. The simplest way of implementing EPD is to set a threshold value in each buffer of the switch. The first packet of any incoming frame is discarded when the fill rate of the buffer exceeds the threshold value. Once the first packet of a frame is discarded, the remaining packets of the frame are also discarded, even if the fill rate has decreased to below the threshold. However, a packet is not discarded if the first packet of the same frame has been accepted, unless the entire buffer is full. The threshold value should be chosen in such a way that, on the one hand, no buffer overflow occurs and, on the other hand, no corrupted frames are transmitted. For those interested in the subject, a detailed description of the EPD method can be found, for example, in an article by A. Romanow and S. Floyd, Dynamics of TCP Traffic over ATM Networks, Proc. ACM SIGCOMM '94, pp. 79-88, August 1994. One drawback of the EPD method Is that it deals unfairly with the different users. This is due to the fact that the EPD scheme discards complete frames from all connections, without taking into account their current rates or their relative shares in the buffer, i.e. without taking into account their relative contribution to an overload situation. To remedy this drawback, several varia¬tions for selective drop policies have been proposed. Nevertheless, the EPD method and its variations still have the dis¬advantage of being restricted for use only in association with the buffers of the switch, the method becoming active only when the fill rate of a buffer exceeds the threshold. The EPD method and its variations have been studied assuming that the switch is an output-buffered full speed switch, i.e. that the switch ca¬pacity equals to the dimension (number of output/input ports) of the switch. A further drawback relating to this type of switch is that the internal switching speed of the switch becomes high if the dimension of the switch is large. This in turn means that powerful (and expensive) chips must be used. Summary of the invention The purpose of the invention is to eliminate the above-mentioned drawbacks and to create a new method which makes it possible to obtain a frame level performance equal to that of the above prior art methods by means of a less complex and less expensive switch structure, and without the need to control the fill rates of individual buffers. This goal can be attained by using the solution defined in the inde¬pendent patent claims. According to the invention, a frame drop mechanism is Introduced into a switch having a capacity smaller, preferably essentially smaller than the number of inputs and outputs of the switch. This is done so that the first packet of one or more frames Is discarded If the number of packets simultaneously destined for the same port of the switch exceeds a predetermined value (the switch capacity). Once the first packet of a frame has been discarded, the re¬maining packets of the same frame are discarded when they access the switch, regardless of the current buffehng capacity of the switch, i.e. the other packets of corrupted frames are prevented from entering the switching fabric. In other words, the idea of the invention Is to Introduce a drop mechanism into the switching fabric so that the variable which controls the ac¬tivation and deactivation of the drop mechanism indicates the number of pack¬ets simultaneously contending for the same port. This port can be an output port of the whole switch or any output port within the switching fabric. As the feature of several packets contending simultaneously for the same port relates only to output-buffered switches, the switch according to the invention must be an output-buffered switch. By means of the solution according to the present Invention, the implementation simplicity generally characteristic of input-queued switches, the good throughput performance generally characteristic of output-queued switches, and a low frame loss rate can be combined in a single switch more efficiently than before. Implementation simplicity can be improved, as the internal switching speed of the switch according to the Invention Is not proportional to the dimen¬sion of the switch but to the capacity of the switch, which is smaller, preferably much smaller, than the dimension. The switch according to the invention is preferably based on a knockout type structure, as this kind of structure can easily be modified to fulfill the functionality required by the Invention. Brief description of the drawings In the following, the Invention and its preferred embodiments are described in closer detail with reference to examples shown in the appended drawings, wherein Figure 1 illustrates the relationship between packets and frames as used here, Figure 2 shows the general architecture of a Knockout switch, Figure 3 is a block diagram of a single output module of a Knockout switch, Figure 4 is a flow chart illustrating the steps of the method according to the invention, Figure 5 shows a preferred embodiment of the switch according to the pres¬ent invention, Figures 6a to 6d Illustrate the states of an individual switching element of a pri¬oritized Knockout concentrator, Figure 7 illustrates the classification of packets in the switch of Figure 5, Figure 8 illustrates one possible implementation of the acknowledgment dis¬tributor of Figure 5, Figure 9a...9d illustrate the frame drop process in the switch according to the invention. Figure 10 illustrates a second preferred embodiment of the switch according to the invention, Figure 11 is a block diagram of an individual packet filter of Figure 10, Figure 12 is a flow chart illustrating the functions of an individual packet filter of Figure 10, and Figure 13 illustrates the routing of acknowledgments in the output module of Figure 10. Detailed description of the invention As indicated above, the method according to the present invention is used in an output-buffered switch which switches fixed-length packets from N inputs to N outputs. In other words, the switch can be any packet switch suitable for switching fixed-length packets, such as an ATM switch. Further, the switch capacity L, which is defined as the maximum number of packets that can be transmitted simultaneously to one output port in one time slot, is smaller than N, i.e. L As known, the design of the Knockout switch is based on the knockout principle: if the arrivals of packets on N different input lines are statis- tically independent, the probability is extremely low that more than a handful of simultaneous packets, i.e. L packets (L«N), are destined for any particular output port, even for arbitrarily large dimensions (NxN) of the switch. The basic structure of the Knockout switch is illustrated in Figure 2. A packet arriving at one of N inputs is placed onto a broadcast bus from which it is transferred to each of the N output modules OM, {i=1,2,..N). The output modules read the header of the packets, accepting those packets destined for that output and buffering those packets which cannot be immediately placed onto the output link, i.e. when two or more packets are contending simultane¬ously for the same output. A block diagram of an output module OM, is shown in Figure 3. Each of the Input buses is connected to a packet filter PF, (i=1,2,..N), i.e. there are N packet filters at the input of each output module. Each packet filter reads the header of the arriving packet and delivers it to a concentrator CC if the header indicates that the packet is intended for that output. Othenwise, the packet is ignored. Consequently, packets that appear at the outputs of the packet filters of a certain output module belong to the switch output being served by that particular output module. The concentrator comprises N inputs but only L (L The outputs of the concentrator are connected to a shifter SH hav¬ing L inputs and L outputs. As the concentrator fills its left-most outputs first, the left-most buffers would tend to fill up if the packets were connected directly from the concentrator to the L output buffers. The purpose of the shifter is to make sure that the L output buffers OBi (i=1,2,...L) are filled as evenly as pos¬sible. The output line 01, connected to the outputs of the output bufl'ers fetches packets cyclically from the output buffers; in time slot 1 the output line fetches a packet from buffer 0B„ in time slot 2 a packet from buffer OBj, and so on. After the output line has fetched a packet from the last (L"^) buffer, the next packet is again fetched from the first buffer (OBi). As the Knockout switch is widely-known, an interested reader can find detailed descriptions from the many articles or books describing its archi¬tecture and functionality. The Knockout switch is also described in U.S. patent 4,760,570. Therefore, the features of the Knockout switch are not described in more detail here. Instead, the following description describes the modifications introduced to the Knockout architecture by the present invention. According to the present invention, whole frames are discarded in the switch, instead of dropping packets randomly as is done in the Knockout switch. The frames are discarded in such a way that the switch begins to drop the first packet of one or more frames randomly, if the number of packets si¬multaneously destined for an output port exceeds the switch capacity L. The switch identifies the frames to which the discarded packets belong and contin¬ues to discard the other packets from those frames. This functionality is de¬scribed in more detail in the following. Whenever the number of incoming packets destined simultaneously for the same output port exceeds the switch capacity L, the switch begins to discard (knock out) the first packets of some of the incoming frames. Once a first packet of a certain frame is discarded {knocked out), the remaining pack¬ets of the same frame are also discarded when they access the switch, even if the switch would have enough buffering capacity to accept said packets. How¬ever, a packet is never discarded if the first packet of the same frame has al¬ready been accepted by the output port of the switch, unless the entire buffer in question is full. To prevent the packets of corrupted frames from entering the switching fabric, each input port of the switch checks whether the packet leav¬ing for the switch belongs to a corrupted frame, i.e. whether the first packet of the frame which the packet belongs to was discarded earlier in the switch fab¬ric. Therefore, there are no packets entering the switching fabric that belong to a corrupted frame. Figure 4 is a flow chart illustrating the basic principle of the inven¬tion. The switch continuously discards incoming packets which belong to cor¬rupted frames (phases 41 and 42). Should the number K of packets simulta¬neously destined for an output port exceed the switch capacity L, the switch discards a certain number of first packets of frames (i.e. (K-L) packets) by choosing the first packets to be discarded randomly (phases 43 and 44). In other words, the (K-L) frames to be discarded are chosen randomly. As ex¬plained below, there are always at least (K-L) first packets in competition for a port when K is greater than L. In Figure 4, the drop process is divided into two consecutive steps, as these steps are performed in different parts of the switch. In order to be able to check whether an incoming packet belongs to a corrupted frame, the input port of the switch must know if a previous packet of the same frame was accepted or discarded in the switching fabric. In other words, acknowledgments must be sent from the switching fabric to the input ports. The above principle can be implemented in several ways. In the following, two preferred embodiments based on the Knockout switch are shown in more detail. Figure 5 shows the first embodiment, comprising a Knockout switch KS, N input modules IM, (1=1,2,...N), one for each input bus of the Knockout switch, and an acknowledgment distributor AD. In this embodiment the input modules perform step 1 of Figure 4, whereas the concentrators perform step 2. The knockout switch KS of Figure 5 is otherwise similar to the commonly known Knockout switch, except that the concentrators PCi (i=1,2,...N)dropfirst packets of frames, instead of dropping packets randomly. To achieve this, what are known as prioritized concentrators must be used, and the incoming packets must be divided into two classes in terms of loss probability, i.e. a high priority class and a low priority class. The division is done so that the incoming first packet of each frame is marked as a low priority packet and the remaining packets (i.e. those which are not the first packet in a frame) are marked as high priority packets (if not discarded before that). The internal structure of a prioritized concentrator is similar to that of a common Knockout concentrator, except that the internal 2x2 switching elements function so that a high priohty packet always wins the competition against a low priority packet. Therefore, a low priority packet is passed to the next level of competition only when no high priority packet is present at the in¬puts of a 2x2 switching element. If two high-priority packets are present at the inputs of a 2x2 switching element, the packet at the right Input loses the com¬petition. Figures 6a to 6d illustrate the states of an individual switching ele¬ment SE of a prioritized concentrator PCi, assuming that a packet is present at both inputs. The classification of the packets is illustrated in Figure 7, where Kh represents the number of high-priority packets and Kl the number of low-priority packets destined for a particular output In a single time slot. In the pri¬oritized concentrators PC,, (K-L) low priority packets are dropped if K>L. It is to be noted that high priority packets wjil never be dropped in the concentrators because the number of contending high priority packets will never exceed L. This is because all other packets (which would be marked as high priority packets) of corrupted frames are not allowed to enter the switch¬ing fabric. This is also why there are always at least (K-L) first packets in the competition for an output if K is greater than L. This can be proved as follows: If K>L, there are two alternatives depending on the value of Kh, (1) let us assume that Kh>L. This would mean that the number of packets accepted by the switching fabric in the previous time slot is greater than the switch capacity (as one output port of the switch can only accept up to L simultaneous packets). Therefore, this assumption is false. (2) let us assume that Kh K-L, i.e. there are at least (K-L) low priority packets (first packets) in competition for the output. The acknowledgment distributor AD, which is common to all output nnodules, has NxL inputs and N outputs. The first L inputs are connected to the outputs of the concentrator of the first output module, the next L inputs to the outputs of the concentrator of the second output module, etc. If a packet passes through a concentrator PCi, an acknowledgment Is generated and sent through the distributor to the correct input module. The acknowledgment distributor AD can be, for example, a simple crossbar matrix, as shown in Figure 8. There is only one connection in each row and column in the crossbar matrix in eadi time slot. Figure 8 shows how an acknowledgment is transferred If a packet from input module IM2 is ac¬cepted by output module OM,. It is assumed that the packet will emerge from the output L of the concentrator of said output module. An acknowledgment message will then be generated at said output, the message Including, in ad¬dition to other data, the address of the input port from which the packet arrived (i.e. source address). On the basis of this source address, the switching ele¬ment (marked with a circle in Figure 8) corresponding to the source address connects the message to the correct input module. It is thus to be noted that the self-routing tag attached to the packets (in the input modules) includes the addresses of both the input and the output ports. In each time slot, each input module IM, (1=1,2,,..N) checks whether the packet leaving for the switch is the first packet of a frame. If this is the case, the input module marks the packet as a low priority packet and passes it to the switching fabric. If the packet is not a first packet of a frame, the input module checks, using the received acknowledgments, whether the previous packet belonging to the same connection was discarded in the switch. If the previous packet was discarded, the input module discards the packet, but if the previous packet was accepted, the input module marks the packet as a high-priority packet and passes it to the switching fabric. As shown in association with input module IM^ in Figure 5, the above mentioned functionality can be implemented, for example, by means of a separate control unit CU which receives the acknowledgments, reads the header of the packet which is at the tip of the input buffer IB, and marks or dis¬cards said packet. Figures 9a...9d illustrate an example of the frame drop process in the switch according to the invention. In this example, the switch has four in¬puts and four outputs, and the switch capacity L equals two. Low priority pack¬ets are shown as hatched, and the numbers inside the packets indicate the output port which Is the destination of the packet. In time slot 1 (Figure 9a), the two packets destined for output 1 are accepted because L=2. In time slot 2 (Figure 9b), three packets are heading for output 1, so one of them must be discarded. In this case, the packet from input 2 is discarded in the concentrator, because it is the only low priority packet (first packet of a frame). The two other packets are accepted because they are not the first packet of a frame and because the preceding packets in the same frames were accepted. In time slot 3 (Figure 9c), the packet from in¬put 2 is dropped at the input port 2 because the previous packet of the frame was dropped. In time slot 4 (Figure 9d), the packet from input 2 is again dropped, for the same reason. Nevertheless, there are still three packets des¬tined for output 1. The packet from input 1 is accepted because it is a high pri- ority packet, whereas one of the two first packets contending for output 1 is randomly dropped. In the embodiment of Figure 5, the switch utilizes a large central¬ized acknowledgment distributor. Alternatively, the drop mechanism can be performed in the output modules only. This embodiment is illustrated in Figure 10, which shows one output module of such a switch. The overall structure of the switch is that shown in Figure 2, As shown in Figure 10, each output mod¬ule comprises N packet filters PF', (i=1,2,...,N), a prioritized concentrator PCi with N inputs and L outputs, a shifter, L output buffers, and an acknowledg¬ment distributor AD, with L inputs and N outputs. In this case, the packet filters perform step 1 of Figure 4, whereas the prioritized concentrator performs step 2. As the Knockout switch, the packet filters PF', accept packets destined for that output and ignore the rest. However, as compared to the known packet filter of the Knockout switch, each packet filter PF', has some additional features. Firstly, a packet filter prevents a packet from a corrupted frame from entering the concentrator. Secondly, a packet filter marks the first packet of frames as low priority packets and other packets as high priority packets. Figure 11 is a block diagram of an individual packet filter PF',, and Figure 12 is a flow chart illustrating the functions of an individual packet filter. An address filter 101 reads the destination address of the incoming packet and checks whether the packet is destined for the output in question (phase 110). If this is the case, the packet is forwarded to an identification unit 102, which identifies the packets which are the first packet of frames (phase 111) by reading the headers of the incoming packets. For example, if the packets are ATM cells, the third bit of the PTI field of the cell header indicates whether the cell is the last cell segmented from a larger data unit. Packets which are not first packets are transferred for a further check to a marking unit 103 (phase 112). In this further check the acknowl¬edgment information on the previous packet of the same connection is checked. If the previous packet has been accepted, the packet is marked with a high priority stamp (phase 114) and supplied to the output of the packet filter. Othenwise, the output of the filter is not enabled, i.e. the packet is prevented from entering the concentrator (the packet is discarded). Packets identified as first packets bypass the acknowledgment check and are directly marked with a low priority stamp before being supplied to the output of the packet filter. The following table describes the operation of the packet filter in various situations. Input Acknowledgment Priority status/discard Output first packet 1 low-priority first-packet first packet 0 low-priority first packet other packet 1 high-priority other packet other packet 0 discard no packet packet does not belong to the out¬put, or no packet on the input 1 discard no packet packet does not belong to the out¬put, or no packet on the input 0 discard no packet 1: previous packet has been accepted 0: previous packet has been discarded or no packet has been accepted In the second embodinnent of the switch (Figure 10), the prioritized concentrator operates in the same way as in the first embodiment (Figure 5), i.e. it performs step 2 of Figure 4. In the second embodiment, the acknowledgment distributors are distributed to every output module. Each distributor AD, can be a simple LxN crossbar network with inputs connected to the outputs of the concentrator and outputs connected to the packet filters. If a packet passes through the con¬centrator PCj , an acknowledgment is generated and sent back through the distributor to the packet filter from which the packet came. Figure 13 illustrates an example of the acknowledgment feedback path. The route of the packet is shown by a thick dashed line and the route of the acknowledgment by a thin dashed line. Although the invention has been described here in connection with the examples shown in the attached figures, it is clear that the invention is not limited to these examples, as it can be varied in several ways within the limits set by the attached patent claims. For example, the principle described above can also be applied to the individual switching elements of a multistage switching fabric. Depending on the basic structure of the switch to which the invention is applied, the switch may need a separate means for counting the number of simultaneously contending packets, i.e. the load level, so that the drop mechanism can be activated when the threshold is exceeded. However, a switch structure based on the knockout type switch is preferable in that no separate means are needed for measuring the load level. The switch can also have an additional drop mechanism which monitors the fill rates of the output buffers and drops packets from said buffers, i.e. the switch can have two su¬perimposed drop mechanisms. WE CLAIM: 1, A frame discard method for a packet switch, the method comprising the steps of receiving packets belonging to at least one transmission connection consecutive packets of an individual transmission connection forming frames; switching packets iron input ports of the switch to N output ports of the switch, through at least one intermediate port; wherein the maximum number of packets that can be transmitted simultaneously to one port is smaller than N, the method comprising the steps of a) selecting and discarding a first packet of a frame when the number of packets simultaneously contending for an individual port exceeds said maximum number; and b) further discarding the remaining packets of the same frame, once said first packet of said frame has been discarded, regardless of the current buffering capacity of the switch. 2. The method as claimed in claim 1, wherein at least one first packet of a frame is chosen randomly from among packets which are the first packet of a frame. 3. The method as claimed in claim 1, wherein the other packets belonging to a frame whose first packet has been switched through the switch are discarded only if the switch has no buffering capacity for said packets, 4, The method as claimed in claim 3, wherein the packets received are classified as high and low priority packets and supplied to a Knockout switch comprising Knockout concentrators in which packets compete pairwise in such a way that the high priority packet wins the low priority packet whenever high and low priority packets compete against each other. 5, The method as claimed in claim 1, wherein said remaining packets are discarded at the input edge of the switch to prevent them from entering the switch, 6, A packet switch for switching packets, the switch comprising N mput ports, N output ports, and at least one intermediate port between the input ports and the output ports, whereby the maximum number of packets that can be transmitted simultaneously to one port of the switch is smaller than N, characterized in that the switch comprises first means (IMi, PCI,.,.PCN; PF'|..,PF'N, PCi) for discarding at least one first packet of a frame when the number of packets simultaneously destined for an individual port exceeds said maximum number, and second means (AD, IM|; ADi, PF'i,-PF'fj) for discarding the remaining packets of a frame, if the first packet of the same frame has been discarded, 7, The packet switch as claimed in claim 6, wherein said first means comprises a classifier for dividing the packets received into low and high priority packets, and Knockout concentrators (PC],,, PCN; PC]) comprising elements (SE) in which packets compete pairwise in such a way that a high priority packet always wins over a low priority packet when said packets compete against each other, 8, The packet switch as claimed in claim 7, wherein the switch comprises N parallel buses and N output modules, each output module being connected to each of the buses and comprising a Knockout concentrator, and N input modules, each being connected to one of the input buses and each comprising said classifier, 9, The packet switch as claimed in claim 8, wherein the second means comprise a centralized distributor connected to the outputs of the Knockout concentrator of each output module for routing acknowledgements from each concentrator to the input modules, said acknowledgements containing information on packets having passed the concentrators. 10. The packet switch as claimed in claim 9, wherein the centralized distributor is a crossbar matrix.

Documents:

2550-mas-1998 abstract.jpg

2550-mas-1998 abstract.pdf

2550-mas-1998 claims duplicate.pdf

2550-mas-1998 claims.pdf

2550-mas-1998 correspondence others.pdf

2550-mas-1998 correspondence po.pdf

2550-mas-1998 description (complete) duplicate.pdf

2550-mas-1998 description (complete).pdf

2550-mas-1998 drawings duplicate.pdf

2550-mas-1998 drawings.pdf

2550-mas-1998 form-19.pdf

2550-mas-1998 form-2.pdf

2550-mas-1998 form-26.pdf

2550-mas-1998 form-4.pdf

2550-mas-1998 form-6.pdf

2550-mas-1998 petition.pdf