(12) United States Patent
`Shalom
`
`US006876669B2
`(10) Patent No.:
`US 6,876,669 B2
`(45) Date of Patent:
`Apr. 5, 2005
`
`(54) PACKET FRAGMENTATION WITH NESTED
`INTERRUPTIONS
`
`(75) Inventor: Rafi Shalom, Ramat Gan (IL)
`
`(73) Assignee: Corrigent Systems Ltd., Tel Aviv (IL)
`(*) Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 794 days.
`21 Ap1. No.: 09/756553
`(21) Appl. No.: 09/756,
`(22) Filed:
`Jan. 8, 2001
`(65)
`Prior Publication Data
`US 2002/0131425A1 Sep. 19, 2002
`(51) Int. Cl.................................................... H043/16
`(52)
`... 370/468; 370/473; 370/474
`(58) Field of Search ................................. 37052, ss,
`370/434, 435, 465, 466, 468, 394, 473,
`474
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,173,898. A 12/1992 Heinzmann et al.
`5,343,473 A * 8/1994 Cidon et al. ................ 370/465
`5,497,371. A * 3/1996 Ellis et al. .................. 370/412
`5,557.608 A * 9/1996 Calvignac et al. .......... 370/389
`5,734,867 A : 3/1998 Clanton et al. ............. 370/461
`5. A 4/1998 child et h - - - - - - - - 370/329
`E. A 12: EY".tal.
`6.212,190 B1
`4/2001 Mulligan
`6,366,589 B1
`4/2002 Naudus, Jr. et al.
`
`4/2003 Chang
`6,553,003 B1
`6,594,249 B1 * 7/2003 Goldberg .................... 370/345
`6,594.278 B1 * 7/2003 Baroudi .....
`... 370/466
`6,631,132 B1 * 10/2003 Sourani .....
`... 370/389
`6,633,564 B1 * 10/2003 Steer et al. ................. 370/389
`6,654,811 B1 11/2003 Chaskar et al.
`2002/0041595 A1
`4/2002 Delvaux ..................... 370/392
`2003/O103515 A1
`6/2003 Brown et al.
`OTHER PUBLICATIONS
`The ATM Forum Technical Committee, “Inverse Multiplex
`ing for ATM (IMA) Specification, Version 1.0",
`AF-PHY-0086.000, Jul. 1997, pp. 1-135.
`Sklower, K. et al., RFC 1990, “The PPP Multilink Protocol
`(MP)”, pp. 1–25, Aug. 1996.
`* cited by examiner
`Primary Examiner-Chau Nguyen
`Assistant Examiner-Christine Ng
`(74) Attorney, Agent, or Firm-Darby & Darby
`(57)
`ABSTRACT
`A method for transmitting data over a channel includes
`receiving a first datagram for transmission at a first priority,
`and receiving a Second datagram for transmission at a
`Second priority, higher than the first priority, before the
`transmission of the first datagram is completed. The first
`datagram is divided into a plurality of fragments, including
`a first fragment and a last fragment. The fragments of the
`first datagram are transmitted over the channel, beginning
`with the first fragment. At least a fragment of the Second
`datagram is transmitted over the channel before transmitting
`the last fragment of the first datagram.
`
`27 Claims, 3 Drawing Sheets
`
`50
`
`TRANSTER
`
`
`
`28
`ey - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`FRAGMENTER
`WITH
`PRIORITY
`HANDLING
`
`!
`
`EX 1001 Page 1
`
`

`

`U.S. Patent
`US. Patent
`
`Apr. 5, 2005
`Apr. 5, 2005
`
`Sheet 1 of 3
`Sheet 1 0f 3
`
`US 6,876,669 B2
`US 6,876,669 B2
`
`08
`cm
`
`§\\
`
`F""""""""’""1
`---------------------
`
`cNW
`
`EEQME
`
`_H?rIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`|----------------------------------- ––––––––––––––––––––––––
`
`
`E:as:F.0E
`
`EX 1001 Page 2
`
`EEEE
`4.mEaaaW"
`
`lllllllllllllllllllllllllllllllllllllllllllllllllllllllL
`
`EmaEz"
`
`
`a.a.Eggmzéb
`
`-1
`
`
`
`
`
`
`
`
`
`EX 1001 Page 2
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 5, 2005
`
`Sheet 2 of 3
`
`US 6,876,669 B2
`
`--------
`
`HÇITHWCHSSW}}}
`
`|-------------------------------------i No.
`
`92
`
`
`
`
`
`
`
`
`
`| | | { | | | | | | † | | | |
`
`39
`
`- - - - - - - - - - - - - - -
`
`HALIM
`
`ÅLIH01Md
`
`?NITOINWHL
`
`NJ
`
`09
`
`
`
`ses as - s is as - - - - - - rs -
`
`EX 1001 Page 3
`
`

`

`U.S. Patent
`
`Apr. 5, 2005
`
`Sheet 3 of 3
`
`US 6,876,669 B2
`
`RECEIVE FRAGMENT
`
`
`
`
`
`l, O OF
`CURRENT END
`FRAGMENT
`
`AND NOT HANDLED
`N as Roy)
`
`FOR CURRENT END
`FRAGMENT
`
`BEGINNING
`RAGMENT RECEIVED WIT
`SNB C SN, =
`
`OSCARD ALL
`FRAGMENTS
`WITH | >
`AND SNKSN
`
`NO
`
`IS
`HIS THE
`N01 RAGMENT JUST
`RECEIVED
`
`BEGINNING
`FRAGMENT RECEIVED WITH
`
`
`
`
`
`
`
`0+
`FRAGMENTS
`RECEIVED IN (SN, SN)
`WITH =
`?
`
`
`
`REASSEMBLE
`PACKET
`
`MORE THAN
`ONE BEGINNING
`FRAGMENT WITH
`SNB g SN, =
`
`
`
`
`DISCARD ALL
`FRAGMENTS
`WITH =
`LARGEST SNB
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISCARD ALL
`FRAGMENTS
`WITH =
`
`EX 1001 Page 4
`
`

`

`1.
`PACKET FRAGMENTATION WITH NESTED
`INTERRUPTIONS
`
`US 6,876,669 B2
`
`2
`FIG. 1 as M, which is seen to increase from 4 to 5 to 6 to
`9 as fragments 42 arrive in sequence over the links. When
`ever an ending (E) fragment arrives, the reassembler checks
`the SN of the ending fragment against M. When M is greater
`than the SN of the ending fragment (SN), and the remaining
`fragments in the packet to which the ending fragment
`belongs have not yet arrived, the missing fragments are
`considered to have been lost. All of the fragments whose
`Sequence numbers are less than or equal to SN are then
`discarded. For example, if in the scheme shown in FIG. 1,
`the fragment with SN=5 had failed to arrive at the receiver,
`then when M=9, the ending fragment of packet 34 (SN=7),
`which was previously received, would meet the criterion
`M>SN. All of the fragments belonging to packet 34 (SN=4,
`6 and 7) would then be discarded.
`In order for this method of reassembly and lost fragment
`detection to work properly, it is necessary that transmitter 22
`Send the fragments strictly in order of their sequence num
`bers. All of the fragments of each packet must therefore be
`Sent without interruption before the transmitter begins send
`ing the fragments of the next packet. As a result, when the
`ending fragment is received, the receiver is assured that all
`of the fragments in the packet have already been transmitted.
`If M increases past SN without all of the fragments in the
`packet having arrived, then it can be safely assumed that one
`or more of the packets have been lost.
`SUMMARY OF THE INVENTION
`It is an object of the present invention to provide
`improved methods and Systems for datagram fragmentation
`and reassembly, particularly for multilink data transmission.
`It is a further object of Some aspects of the present
`invention to provide enhanced Support for fragmentation and
`transmission of datagrams at multiple priority levels.
`In preferred embodiments of the present invention, a data
`transmitter and receiver exchange datagrams, typically data
`packets, over a channel at multiple priority levels. The
`transmitter determines during transmission whether each of
`the packets should be divided into fragments for transmis
`Sion to the receiver, depending on packet traffic and priori
`ties and other system conditions. The receiver then reas
`Sembles the packets as necessary, based on information
`contained in the fragment headers. The decision as to
`whether a packet should be fragmented and in what manner
`is preferably made by the transmitter “on the fly.” By
`contrast, prior art transmitters work with fixed fragment
`Sizes and require that the decision to fragment or not to
`fragment the packets be made statically, before beginning
`operation.
`In particular, when the transmitter receives a high-priority
`packet for transmission while in the midst of transmitting a
`lower-priority packet, the lower-priority packet is preferably
`fragmented. The transmission of the fragments of the lower
`priority packet is interrupted in order to send the high
`priority packet fragments immediately. As a result, the order
`of transmission of the packet fragments need not follow the
`order in which the packets were received by the transmitter.
`Transmission of the fragments of the lower-priority packet is
`typically completed after the high-priority packet has been
`Sent. Priority information in the fragment headers enables
`the receiver to identify interruptions, so as to reassemble the
`packets and detect lost fragments even when the fragments
`are not transmitted in the order of the original packet
`Sequence.
`Preferred embodiments of the present invention are par
`ticularly advantageous in multilink transmission settings.
`
`15
`
`FIELD OF THE INVENTION
`The present invention relates generally to high-speed data
`transmission, and specifically to methods and systems for
`multiplexing of data streams with different priorities over a
`Single channel.
`BACKGROUND OF THE INVENTION
`A number of methods are known in the art for aggregating
`multiple physical links into a single logical channel between
`a transmitter and a receiver. Data are split at the transmitter
`into multiple streams, each of which is transmitted over a
`respective one of the physical links. The receiver then
`reassembles the data into the original order. The use of
`multiple parallel links is advantageous in providing high
`channel bandwidth when only low-bandwidth links are
`available, and also assists network operators in offering
`flexible data rates and bandwidth on demand.
`Standard methods for multilink transmission of this sort
`have been defined for both Asynchronous Transfer Mode
`(ATM) and Internet Protocol (IP) networks. The ATM
`25
`approach is described in document AF-PHY-0086.001, pro
`mulgated by the ATM Forum (1999), entitled “Inverse
`Multiplexing for ATM (IMA) Specification Version 1.1.”
`For IP networks, the “PPP Multilink Protocol' is described
`by Sklower et al. in Request for Comments (RFC) 1990 of
`the Internet Engineering Task Force (IETF). Both of these
`documents are incorporated herein by reference.
`FIG. 1 is a block diagram that Schematically illustrates a
`System 20 for multilink data communications in accordance
`with the PPP Multilink Protocol, as is known in the art. A
`35
`transmitter 22 transmits data over a multilink channel 24 to
`a receiver 26. Channel 24 comprises multiple physical links
`28, 30,32. A fragmenter 40 breaks incoming packets 34, 36,
`38 into fragments 42 for transmission over the different
`physical links. Each fragment 42 receives a Multilink Pro
`tocol (MP) header that includes a fragment sequence number
`(SN), a beginning bit (B) and an ending bit (E). The SN is
`incremented for each fragment in the sequence. In the
`example shown in FIG. 1, SN runs from 4 to 13. Packet 34
`is divided into fragments 4–7, packet 36 into fragments
`8–10, and packet 38 into fragments 11-13. The first frag
`ment in each packet receives B=1, while the last segment
`receives E=1. Otherwise, B and E are set to zero. When a
`fragment contains an entire packet, both B and E are set to
`1.
`Transmitter 22 sends fragments 42 over channel 24 in the
`order of their sequence numbers. There is no assurance,
`however, that the fragments will arrive in order at receiver
`26, and Some of the fragments may be lost entirely. A
`reassembler 44 in receiver 26 waits until all of the fragments
`55
`in a given packet have arrived before rebuilding the entire
`packet. (Although for the sake of conceptual clarity, frag
`menter 40 and reassembler 44 are shown and described
`herein as distinct functional blocks, the functions of these
`blocks are typically carried out along with other functions by
`central processing units (CPUs) in transmitter 22 and
`receiver 26, respectively.) If reassembler 44 determines that
`any of the fragments in the packet have been lost, the rest of
`the fragments in the packet are discarded.
`In order to detect lost fragments, reassembler 44 keeps
`track of the minimum over all of links 28, 30 and 32 of the
`most recently received SN. This minimum is identified in
`
`40
`
`45
`
`50
`
`60
`
`65
`
`EX 1001 Page 5
`
`

`

`3
`Use of the present invention enables delay-Sensitive
`Services, Such as voice, to be transmitted with minimal delay
`over multilink channels that are also used to provide high
`Volume, delay-insensitive Services, Such as Web browsing
`and electronic mail. As noted above, the PPP Multilink
`protocol, like other datagram fragmentation methods known
`in the art, requires that fragments be transmitted in packet
`order. Under Such conventional methods, once the transmit
`ter has begun Sending fragments of a given packet, it cannot
`Stop until the entire packet has been Sent. Thus, the only way
`that a high-priority packet can be assured immediate trans
`mission is by discarding any low-priority packets whose
`transmission is in progreSS. The multi-priority approach of
`the present invention, however, allows the transmitter to Stop
`Sending the low-priority packet in the middle, and then to
`complete the transmission after high-priority requirements
`have been Serviced. This added responsiveness to high
`priority requirements is especially important in the presence
`of low-Speed channels and long, low-priority packets.
`In Some preferred embodiments of the present invention,
`three or more priority levels are defined. Transmission of
`packet fragments at a given level can be interrupted, as
`described above, by another packet at any higher level.
`"Nested” packet interruptions are also Supported, whereby a
`low-priority packet is interrupted by a medium-priority
`packet, which is in turn interrupted by a high-priority packet,
`following which all of the transmissions are completed.
`Substantially any number of Such nested priorities can be
`Supported without compromising the ability of the receiver
`to reassemble all of the packets.
`There is therefore provided, in accordance with a pre
`ferred embodiment of the present invention, a method for
`transmitting data over a channel, including:
`receiving a first datagram for transmission at a first
`priority;
`receiving a Second datagram for transmission at a Second
`priority, higher than the first priority, before the transmission
`of the first datagram is completed;
`dividing the first datagram into a plurality of fragments,
`including a first fragment and a last fragment;
`transmitting the fragments of the first datagram over the
`channel, beginning with the first fragment; and
`transmitting at least a fragment of the Second datagram
`over the channel before transmitting the last fragment of the
`first datagram.
`In a preferred embodiment, receiving the first and Second
`datagrams includes receiving Internet Protocol (IP) packets,
`and transmitting the fragments includes distributing the
`fragments for transmission over a plurality of parallel physi
`cal links, wherein the plurality of parallel physical links are
`arranged So as to constitute a single logical channel.
`Preferably, the fragments of the first and Second datagrams
`are received and reassembled at a receiver connected to the
`plurality of parallel physical linkS. Further preferably, trans
`mitting the fragments includes adding an indication to the
`fragments that transmission of the fragments of the first
`datagram was interrupted by transmission of the Second
`datagram, and reassembling the datagrams includes reas
`Sembling the packets responsive to the indication. Most
`preferably, reassembling the datagrams includes detecting
`loSS of a fragment of one of the datagrams on one of the
`links, and discarding other fragments received at the receiver
`responsive to the indication.
`Typically, transmitting at least the fragment of the Second
`datagram includes dividing the Second datagram into mul
`tiple fragments for transmission over the channel.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,876,669 B2
`
`4
`Preferably, transmitting at least the fragment of the Second
`datagram includes interrupting transmission of the frag
`ments of the first datagram until all fragments of the Second
`datagram have been transmitted over the channel.
`Alternatively, transmitting at least the fragment of the Sec
`ond datagram includes interspersing transmission of the
`fragments of the first datagram with one or more fragments
`of the Second datagram, Subject to the first and Second
`priorities.
`In a preferred embodiment, the multiple fragments of the
`Second diagram include first and last fragments, and the
`method includes receiving a third datagram for transmission
`at a third priority, higher than the Second priority, before the
`last fragment of the Second datagram has been transmitted,
`and transmitting at least a fragment of the third datagram
`over the channel before transmitting the last fragment of the
`Second datagram. Preferably, transmitting the at least one
`fragment of the third datagram includes transmitting the at
`least one fragment of the third datagram before transmitting
`the last fragment of the first datagram.
`Preferably, transmitting at least the fragment includes
`interrupting transmission of a number of datagrams, includ
`ing at least the first datagram, in order to transmit at least the
`fragment of the Second datagram, and adding a field to the
`fragment indicating the number of datagrams whose trans
`mission has been interrupted. Further preferably, the method
`includes receiving the fragments of the first and Second
`datagrams at a receiver connected to the channel, and
`reassembling the datagrams from the fragments responsive
`to the field indicating the number. Most preferably, reas
`Sembling the datagrams includes detecting loSS of a frag
`ment having a given value of the number indicated by the
`field, and discarding other fragments received at the receiver
`with the given value of the number indicated by the field.
`Preferably, dividing the first datagram into the plurality of
`fragments including deciding on division of the first data
`gram into the plurality of fragments responsive to receiving
`the Second datagram.
`There is also provided, in accordance with a preferred
`embodiment of the present invention, apparatus for trans
`mitting data over a channel, including:
`a transmitter, coupled to receive first and Second data
`grams for transmission over the channel at respective first
`and Second priorities, wherein the Second priority is higher
`than the first priority, and the transmitter receives the Second
`packet before the transmission of the first packet is
`completed, and adapted to divide the first datagram into a
`plurality of fragments, including a first fragment and a last
`fragment, and to transmit the fragments of the first datagram
`over the channel, beginning with the first fragment, and to
`transmit at least a fragment of the Second datagram over the
`channel before transmitting the last fragment of the first
`datagram; and
`a receiver, adapted to receive the fragments of the data
`grams over the channel and to reassemble the fragments. So
`as to reconstruct the first and Second datagrams.
`The present invention will be more fully understood from
`the following detailed description of the preferred embodi
`ments thereof, taken together with the drawings in which:
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram that Schematically illustrates a
`System for multilink data communications, as is known in
`the art;
`FIG. 2 is a block diagram that Schematically illustrates a
`System for multilink data communications, in accordance
`with a preferred embodiment of the present invention; and
`
`EX 1001 Page 6
`
`

`

`S
`FIG. 3 is a flow chart that schematically illustrates a
`method for reassembling packet fragments received over a
`communication channel, in accordance with a preferred
`embodiment of the present invention.
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`Reference is now made to FIG. 2, which is a block
`diagram that schematically illustrates a system 50 for data
`transmission over multilink channel 24, in accordance with
`a preferred embodiment of the present invention. System 50
`comprises a transmitter 52 and a receiver 54. The transmitter
`comprises a packet Source 56 and a dynamic fragmenter 58
`with priority handling capability. Fragmenter 58 divides
`input packets into fragments for transmission, in a manner
`Substantially Similar to the operation of fragmenter 40,
`shown in FIG.1. In distinction to the operation of transmitter
`22, however, fragmenter 58 is able to determine “on the fly”
`whether and how to fragment a given packet. It uses this
`capability to arrange the order of transmission of the frag
`ments according to the priority levels of the packets, as
`described hereinbelow. Receiver 54 comprises an interrup
`tion handler 60 and a reassembler 62, which restore the
`fragments to their proper order and rebuild the transmitted
`packets from the fragments.
`The particular functional blocks that are shown in FIG. 2
`as elements of transmitter 52 and receiver 54 are selected for
`inclusion here for the Sake of conceptual clarity. They
`represent only a Small part of the functionality of Such a
`transmitter and receiver in actuality. The integration of these
`fragmentation and reassembly functions in actual transmit
`ters and receivers will be apparent to persons of skill in the
`art. By the same token, Such perSons will appreciate that the
`functions of fragmenter 58 may be carried out together by a
`CPU or other processor in the transmitter. Similarly, the
`functions of interruption handler 60 and reassembler 62 may
`be carried out by a CPU or other processor in the receiver.
`These CPUs or processors typically perform other functions,
`as well, as are known in the art.
`Fragmenter 58 generates fragments of packets with dif
`ferent transmission priority levels. For example, one packet
`may be a Voice packet with high priority, while another may
`be a portion of an electronic mail (e-mail) message with low
`priority. If the priority handler begins to receive fragments
`of a high-priority packet from fragmenter 58 while in the
`midst of transmitting a low-priority packet, it preferably
`interrupts the transmission of the low-priority fragments in
`order to Send the high-priority ones. In order to enable
`receiver 54 to reassemble the fragments in the proper order
`and detect any lost fragments, the fragmenter adds a header
`50
`to each fragment containing the following fields:
`Sequence number (SN)-A running index, as in the MP
`header specified by the PPP Multilink Protocol.
`Offset (O)- The sequential number of each fragment
`within a given packet. For the beginning fragment in
`the packet, O is zero (and the B bit specified by the
`Multilink Protocol is thus not needed).
`Ending (E)-Set to E=1 for the last fragment in each
`packet, as specified by the Multilink Protocol.
`Interruption level (I) The number of lower-priority
`packets that a higher-priority packet has interrupted.
`The range of values of this field is given by the number
`of different priority levels supported by fragmenter 58.
`All fragments of a given packet must have the same
`interruption level.
`Table I below presents an example of a Sequence of
`packets transmitted in System 50, illustrating the meaning
`
`6
`and use of the fragment header fields. The Sequence consists
`of six packets, labeled A through F, having different
`(arbitrary) priority levels. Packets A, B, C and F are each
`divided into two fragments. Packet D is divided into three
`fragments, while packet E is Sent as a Single fragment. AS
`Seen below, the transmission of packet A is interrupted by
`packet B and then packet C, packet C is interrupted by
`packet D, and packet D is interrupted by packet E, giving
`three different nesting levels. Packet C does not interrupt
`packet B, since both have the same priority. Packet Farrives
`after transmission of packet A is finished.
`
`TABLE I
`
`Packet
`
`Priority
`
`SN
`
`Offset
`
`Ending
`
`A.
`B
`B
`C
`D
`D
`E
`D
`C
`A.
`F
`F
`
`O
`I
`I
`I
`IV
`IV
`VII
`IV
`I
`O
`VI
`VI
`
`O
`1.
`2
`3
`4
`5
`6
`7
`8
`9
`1O
`11
`
`O
`O
`1.
`O
`O
`1.
`O
`2
`1.
`1.
`O
`1.
`
`O
`O
`1.
`O
`O
`O
`1.
`1.
`1.
`1.
`O
`1.
`
`Int.
`level
`
`O
`1.
`1.
`1.
`2
`2
`3
`2
`1.
`O
`O
`O
`
`In a relatively simple embodiment of the present
`invention, when a low-priority packet is interrupted by a
`higher-priority packet, no further fragments of the low
`priority packet are transmitted until transmission of the
`higher-priority packet is completed. On the other hand, in a
`more flexible embodiment, fragmenter 58 may continue
`transmitting fragments of the low-priority packet if there is
`time available while waiting for packet Source 56 to Supply
`the remainder of the higher-priority packet. In this latter
`embodiment, referring to the example of packets A and B in
`the table above, it might be possible to transmit fragment
`A(1) (the Second fragment of packet A) before fragment
`B(1) if there is a Sufficient gap in time between fragments
`B(0) and B(1). In the simpler embodiment, however, only
`the fragment order given in the table is possible.
`FIG. 3 is a flow chart that schematically illustrates a
`method for packet reassembly, carried out by interruption
`handler 60 and reassembler 62, in accordance with a pre
`ferred embodiment of the present invention. Each cycle of
`the method begins when receiver 54 receives a new
`fragment, at a fragment reception Step 70. The minimum
`value, M, of the SN of the received fragments is updated as
`appropriate, at an update Step 71, in Substantially the same
`manner as is called for by the PPP Multilink Protocol, and
`which is described in the Background of the Invention.
`The interruption handler then checks to determine
`whether receiver 54 has received any ending fragments that
`have not yet been reassembled into a packet, at an ending
`step 72. If so, the interruption handler cycles through all of
`these unreassembled ending fragments in turn. For each of
`the ending fragments detected, its sequence number (SN),
`interruption level (I) and offset (O) are recorded as current
`ending fragment values, at an end processing Step 74, for use
`in processing other, non-ending fragments that have been
`received, as described below. The current value of SN for
`each of these ending fragments is checked against the
`current value of M, at a fragment loss detection step 76. If
`M is less than SN, the current ending fragment is checked
`to determine whether it is the fragment most recently
`received by receiver 74, at a new fragment detection step 77.
`
`US 6,876,669 B2
`
`15
`
`25
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`EX 1001 Page 7
`
`

`

`7
`If So, normal packet reassembly continues, at a normal
`beginning fragment check Step 78. Otherwise, if the current
`ending fragment is not the most recently received fragment,
`the proceSS continues to cycle through any other ending
`fragments at step 72 until it is done. After all of the
`unreassembled ending fragments have been checked, the
`proceSS returns to receive the next fragment at Step 70.
`At step 78, interruption handler 60 next checks the other
`fragments that have been received but not yet reassembled
`into packets to determine, for the current ending fragment,
`whether a beginning fragment has been received with the
`Same interruption level, I, as the ending fragment and with
`a Sequence number SN that is less than SN of the ending
`packet. If no Such beginning fragment is found, the inter
`ruption handler concludes that the beginning fragment for
`the current ending fragment has not yet been received and
`returns to Step 72 to check any further ending fragments. If
`an appropriate beginning fragment has been received,
`however, the interruption handler then checks the number of
`fragments with interruption level I that have been received
`in the range between SN and SN, at a complete packet
`checking step 80. When the complete packet has reached the
`receiver, there should be exactly O+1 Such fragments,
`wherein O is the offset of the current ending fragment, as
`noted above. Again, if not all of the expected fragments have
`been received, the process returns to Step 72. Otherwise,
`once all of the O+1 packets have arrived, they are passed
`to reassembler 62 for rebuilding of the packet, at a reassem
`bly step 82.
`On the other hand, when the interruption handler finds at
`step 76 that MeSN, it may be necessary to discard frag
`ments. In the "simple embodiment” described above (in
`which all fragments at any higher interruption level must be
`transmitted before transmission at a lower interruption level
`can continue), any outstanding fragments for which I>I and
`SNCSN are discarded, at an optional higher level discard
`Step 83. These fragments are discarded because in this
`embodiment, whenever it is found that MeSN for a given
`interruption level I, it necessarily means that fragments
`have also been lost from any higher-priority packets that
`were transmitted before the current ending packet and have
`not yet been reassembled. On the other hand, in the “flexible
`embodiment,” in which the transmitter may alternate
`between Sending fragments with higher and lower interrup
`tion levels, this additional discard of fragments with higher
`interruption levels is not carried out.
`Next, at step 84, the interruption handler determines
`whether a beginning fragment has been received belonging
`to the same packet as the current ending fragment. In other
`words, the interruption handler determines whether a begin
`ning packet has been received with interruption level I and
`with a sequence number SN that is less than SN. If no Such
`beginning fragment is found, then all fragments that have
`been received with interruption level I are discarded, at a
`packet discard Step 86.
`It may also occur that two or more beginning fragments
`have been received that satisfy the criteria of step 84. In this
`case, the interruption handler checks to determine which of
`the beginning fragments has the largest Sequence number
`SN, at a beginning fragment Selection Step 88. This begin
`ning fragment, whose SN is thus closest to the Sequence
`number SN of the current ending fragment, is chosen for
`use in reassembly of the packet. Any fragments having
`interruption level I and Sequence number SN that is leSS
`than the largest SN found at level I cannot belong to the
`current packet, and are therefore discarded, at an exceSS
`fragment discard step 90.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,876,669 B2
`
`8
`After the appropriate beginning packet has been found,
`the interruption handler finally checks the number of frag
`ments with interruption level I that have been received in
`the range between SN and SN, at a complete packet
`checking step 92. As noted above at step 80, there should be
`exactly O+1 Such fragments. If not all of the expected
`fragments have been received, the interruption handler con
`cludes that one or more fragments have been lost. All of the
`packets at interruption level I that have Sequence numbers
`between SN and SN are then discarded, at a final discard
`step 94. Otherwise, if all of the O+1 packets have arrived,
`they are passed for processing to reassembly Step 82.
`In reassembling the transmitted packets, reassembler 62
`can order the fragments according to either the Sequence
`number SN or the offset O. These two fields provide a
`redundant count, and the reassembler preferably checks
`them one against the other to ensure data consistency.
`Alternatively, to reduce the data Volume that must be
`transmitted, the offset field can be eliminated from all
`fragments but the ending fragment. In this case, the B bit
`(eliminated from the scheme described hereinabove) should
`be used to distinguish the beginning fragment from Subse
`quent OneS.
`Although preferred embodiments are described herein for
`the most part with reference to transmission of data packets
`in IP networks, the principles of the present invention are
`likewise applicable to networks and datagrams of other
`types, including transmission of cells in ATM networkS.
`Furthermore, while these preferred embodiments relate spe
`cifically to packet fragmentation for the Sake of multilink
`transmission, the present invention may be applied more
`generally to fragmentation and reassembly of datagrams
`transmitted over other Sorts of packet-Switched networks
`and linkS.
`It will thus be appreciated that the preferred embodiments
`described above are cited by way of example, and that the
`present invention is not limited to what has been particularly
`shown and described hereinabove. Rather, the scope of the
`present invention includes both combinations and Subcom
`binations of the various features described hereinabove, as
`well as variations and modifications thereof which would
`occur to perSons Skilled in the art upon reading the foregoing
`description and which are not disclosed in the prior art.
`What is claimed is:
`1. A method for transmitting data over a channel, com
`prising:
`receiving a first datagram for transmission at a first
`priority;
`receiving a Second datagram for transmission at a Second
`priority, higher than the first priority, before the trans
`mission of the first datagram is completed;