(12) United States Patent
`Steer et al.
`
`USOO6633564B1
`(10) Patent No.:
`US 6,633,564 B1
`(45) Date of Patent:
`Oct. 14, 2003
`
`(54) METHOD AND APPARATUS FOR
`INSERTING PACKETS INTO A DATA
`STREAM
`
`(75) Inventors: David G. Steer, Nepean (CA); Paul M.
`Row, Herts (GB)
`(73) Assignee: Nortel Networks Limited, St. Laurent
`(CA)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/401,856
`1.-1.
`(22) Filed:
`Sep. 22, 1999
`(51) Int. Cl. ................................................ H04L 12/56
`(52) U.S. Cl. ............... 370/389; 370/395.4; 370/395.64;
`370/395.1; 709/238; 707/240
`(58) Field of Search ................................. 370230, 231
`370/235, 300, 389, 392,395.1, 395.4, 395.42,
`395.43, 395.52, 352,469, 470, 471, 474,
`473,395.6, 395.64; 709/238; 707/240
`References Cited
`U.S. PATENT DOCUMENTS
`4,542,380 A * 9/1985 Beckner et al. ...,,,,,,, 340/825.5
`
`(56)
`
`4,642,630 A * 2/1987 Beckner et al. .......... 340/825.5
`4,777,595 A * 10/1988 Strecker et al. ............. 370/474
`5,343,473 A * 8/1994 Cidon et al. ........... 340/825.51
`5,557.608 A * 9/1996 Calvignac et al. .......... 370/389
`6,292.484 B1 * 9/2001 Oliver ........................ 370/389
`
`* cited by examiner
`
`Primary Examiner Alpus H. Hsu
`Assistant Examiner Michael J Molinari
`(57)
`ABSTRACT
`This invention provides a communication network with a
`method and apparatus for interrupting the transmission of an
`existing stream of data to insert interrupting packets which
`may have a higher priority than the existing data Stream. The
`interrupting packets are inserted in the data Stream by
`making use of unused pointer values in common transmis
`sion schemes known as the Data Over Cable Service Inter
`change Specification (DOCSIS) or the Asynchronous Trans
`fer Mode (ATM) adaptation layer 2 (AAL2) format of the
`International Telecommunications Union (ITU) recommen
`dation I363.2. Advantageously, the scheduling of packets is
`significantly simplified and the packet jitter is better con
`trolled which results in a significant improvement in trans
`mission performance.
`
`42 Claims, 13 Drawing Sheets
`
`--
`
`- 184 BYTES ->
`91
`-n.
`
`Y
`
`81
`N
`
`86
`87
`88
`89
`MPEGHEADER POINTERFIELD INTERRUPTING PACKET CONTFIELD
`PUSI = 1
`(SET TO 255)
`#1
`(SET TO2)
`90
`
`-85
`INTERRUPTINGPACKET |
`#2
`
`84
`
`RS. FEC
`16 BYTES
`
`
`
`
`
`
`
`
`
`98
`-85
`MPEG HEG
`is.” INTERRUPTINGPACKET #2 (REMAINDER)
`
`-93
`-94
`s FE NTERRUPN PACKET
`
`92
`FEF,
`
`97
`
`-102
`MPEGHEADER
`PUS = 0
`103
`
`INTERRUPTING PACKET #3
`(REMAINDER)
`
`104
`-93
`
`101
`CONTFIELD
`(SET TOO)
`
`y
`
`-100
`INTERRUPTED PACKET
`(REMAINDER)
`
`99
`
`RS-FEC
`16 BYTES
`
`EX 1008 Page 1
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 14, 2003
`Oct. 14, 2003
`
`Sheet 1 of 13
`Sheet 1 0f 13
`
`US 6,633,564 B1
`US 6,633,564 B1
`
`
`
`S2
`
`6 9 as es H 22
`wéQsEz$25
`mmoSmmmoz<
`L
`2
`e
`sc
`O
`
`y
`
`SE
`
`EX 1008 Page 2
`
`EX 1008 Page 2
`
`
`

`

`U.S. Patent
`US. Patent
`
`mm.m,a0
`
`BM2w%
`
`US 6,633,564 B1
`US 6,633,564 B1
`
`
`
`=<3><mmun—4E:
`
`Fmcw
`
`[Jlll|\
`
`
`mm
`
`85:222H:52:.25:Us;38
`
`
`.$5:82:E5_Ex:
`
`ou888.8uEEma:atE
`
`
`
`25253;:Eg3mma2mm
`mEa68m2.8%Nmasm85.mUS,Ea$2.
`
`
`N.wE
`
`EX 1008 Page 3
`
`EX 1008 Page 3
`
`

`

`US. Patent
`
`m
`
`m
`
`a3
`
`US 6,633,564 B1
`
`m,<md:
`
`3:52$5$2E9:EE_220522:
`
`mTli35$_
`E5:Ea
`[IlliljllllLEN:m:Eo:
`E:E:E323::E:
`
`
`
` mmimmE55:.255.:
`
`EX 1008 Page 4
`
`
`
`
`
`o<o._><n_ES.ad:mm_._.z_on_59$:HE:
`
`E
`
`CD
`
`E E
`
`EX 1008 Page 4
`
`
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 14, 2003
`Oct. 14, 2003
`
`Sheet 4 of 13
`Sheet 4 0f 13
`
`US 6,633,564 B1
`US 6,633,564 B1
`
`
`
`07
`
`
`
`
`
`
`
`|<– SBLÅ8 781 —>|
`
`8TImmtm32Ill
`
`[illk
`
`mmmmaSmm
`
`$32DI_IE:
`
`”E?52288223E256$9328;A/
`
`
`
`3mm3B38.
`
`
`
`um”.-mm
`
`mm_._.>m@—
`
`um:.mm
`
`mm:.>m@—
`
`35m53m:
`
`.5qu238>52”5.525
`.5on£88
`EEEEE$531862A/wm
`5—"PI_m=n_
`
`mm
`
`
`
`
`
` oI.25E5:£38555:8&2
`
`wd:
`
`EX 1008 Page 5
`
`EX 1008 Page 5
`
`
`
`
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`mm.
`
`BM5mS
`
`US 6,633,564 B1
`US 6,633,564 B1
`
`
`
`
`
`
`
`
`
`
`
`w2_._.n5mmmhz_3w:EEG;ESE:M,mugmm:EMEZEENEEquSE..59EVE/E5mmE.EB_uan;aH:.mmBEEEHESm:H288&2A/0mmmmmmmmmmom
`
`mm
`
`
`
`Till$5.:2Illlllv
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`m6:
`
`EX 1008 Page 6
`
`EX 1008 Page 6
`
`
`

`

`US. Patent
`
`Oct. 14, 2003
`
`Sheet 6 0f 13
`
`US 6,633,564 B1
`
`um:.mm
`
`$5M.@—
`
`mm._.>mm:H:.mm
`
`mm
`
`om:.mm
`
`mm:.>m@—
`
`w2_._.m=mmm_._.z_
`Eva:EEDmEHEad:.58
`
`
`
`EOEEZEEEEem:$5?$93:was.
`
`EVE:
`
`Ema—422$:So.—59
`
`53E:mums.
`
`ou_m=n_
`
`5,:E52_u5.:
`
`
`
`
`
`
`
`
`
` 5mmEEa_u5.:Es:Em:$556E5:8%QZEEEE
`
`mm
`
`m.w:
`
`omMKmm
`
`memm—.5quEma—42:55.5erSEEm.Emzzfizoe.5onEva:>32E.H:.mm2E2BEEEHEad:#28ozfimzmmmfié3m:
`
`
`
`
`Ehzam
`
`ESE:HE:
`
`_u_w=n_
`
`Rmm
`
`EX 1008 Page 7
`
`EX 1008 Page 7
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 7 of 13
`
`US 6,633,564 B1
`
`
`
`86
`
`| 6
`
`
`
`|<–— SHLAG V61 —>
`
`78G898/88868| 8
`
`
`
`EX 1008 Page 8
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 14, 2003
`Oct. 14, 2003
`
`Sheet 8 of 13
`Sheet 8 0f 13
`
`US 6,633,564 B1
`US 6,633,564 B1
`
`
`
`Tlll|o3lmm:.>mwv||V_
`
`
`
`{Jllllk
`
`8—m2NEm22:mm:m2
`
` TL8%we
`
`
`NN_m3mgmeas
`
`
`
`
`
`
`
`
`
`T|IEm_lv_3._._mP:mPmtmmmm._.>mmEVE:wz_._.m=mmm_._.z_CE:2w“.moAK
`
`59E::3.25.
`
`
`
`
`
`
`
`EEzmmmHE22:22:28wzfimzmmmhg>._._m_<n_2m“5o$93:duo22
`
`m.m:
`
`
`
`5%:ouad:52m:5293:mP:m_.m._._mm35mmA\
`
`TilEmF|v_§
`
`EX 1008 Page 9
`
`EX 1008 Page 9
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 9 of 13
`
`US 6,633,564 B1
`
`NEW PACKETS
`
`,
`- , ,
`at 0203 .....ON
`
`BLOCK HEADER
`151
`
`SCHEDULER
`150
`
`NEXT BLOCK
`BUFFER
`152
`
`CURRENT BLOCK
`BUFFER
`153
`
`
`
`TRANSMISSION
`
`FIG. 10
`
`EX 1008 Page 10
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 10 of 13
`
`US 6,633,564 B1
`
`START TO FILL
`NEXT BLOCK
`
`(1)
`
`(1)
`
`ANY
`PACKETS IN
`O?
`
`YES
`
`
`
`
`
`
`
`
`
`NO
`
`SETO MODE IDLE,
`AND NO
`INTERRUPT DLE
`BLOCK
`
`PACKET
`IN HIGHER PRIORITY
`O?
`
`NO
`
`GET DATA
`PACKET FROMO
`
`YES
`
`(IDLEMODE) YES (6)
`
`
`
`NEW
`NON-INTERRUPTING
`PACKET
`
`NO
`
`
`
`
`
`
`
`
`
`DOES
`PACKET FILL
`BLOCK?
`
`NO
`
`YES
`
`PSU = 0
`(POINTER - NONE)
`
`(1)
`
`YES
`
`(2)
`
`INTERRUPT MODE?
`
`NO
`
`PUS = 1
`POINTER = PACKET
`
`
`
`YES
`
`(1)
`
`NO
`DOES
`PACKET FILL
`BLOCK?
`
`
`
`
`
`FILL BLOCK
`WITH PACKET
`
`YES
`
`ANOTHER
`PACKET IN CURRENT
`O?
`
`SET ODLEMODE
`FILL TO END OF
`BLOCKWITH IDLE ALL
`EMPTY
`
`LOOK IN ANOTHERO
`SET OF CURRENTO
`NUMBER
`
`
`
`ANOTHERO
`
`FIG. 11 A
`
`EX 1008 Page 11
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 11 of 13
`
`US 6,633,564 B1
`
`SET CURRENTO
`NUMBER
`
`GETPACKETDATA
`FROMO
`
`PUS = 1
`POINTER - PACKET
`
`
`
`DOES
`PACKET FILL
`BLOCK?
`
`
`
`
`
`
`
`FIG. 11B
`
`EX 1008 Page 12
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 12 of 13
`
`US 6,633,564 B1
`
`REDUCE INTERRUPT
`LEVEL BY 1 SET NEXT
`CURRENT ONUMBER
`
`ANOTHER
`PACKET INO
`
`SET CONTINUATION
`FIELD = MON-ZERO
`
`
`
`INTERRUPT
`LEVEL - O
`
`YES
`
`SET CONTINUATION
`FIELD = ZERO
`
`GET (INTERRUPTED)
`PACKET FROMO
`
`
`
`
`
`ANOTHER
`PACKET NO2
`
`
`
`
`
`SET CONTINUATION
`FIELD = 0
`FILL REMANDER OF
`BLOCKWITH NEXT
`PACKETINO
`
`
`
`
`
`
`
`
`
`
`
`
`
`FILL BLOCKWITH
`NEXT PACKETINO
`
`DOES
`PACKET FILL
`BLOCK?
`
`YES
`
`PUSI - O
`(POINTER - NONE)
`
`
`
`
`
`
`
`DOES
`PACKET FILL
`BLOCK?
`
`
`
`YES
`
`PUS = 0
`(POINTER = NONE)
`
`(1)
`
`FILL TO END OF
`BLOCK WITH DLE
`
`FIG. 11C
`
`EX 1008 Page 13
`
`

`

`US. Patent
`
`1
`
`Ef0
`
`US 6,633,564 B1
`
`”ammsz—zmm:E
`
`BE_._._.=sVacs
`
`M3:53
` dz_.5qu2;Eva:CazE5,5033:$8
`
`
`2mm>>._.m_mmuszmta>m._m_>m_._Ezmmmfiz$357:
`
`
`
`.5qu2:;anz<55552dEmmmau
`
`$922:aEmmmzuEm
`
`4,_u2:mm
`
`EB:
`
`
`
` 875mg;m1:;53m3522.2%j:55:$25255:m.DENSE22:52:28EEu528mm
`
`
`
`£255.3:5.2:w:9mS2EH:3"EB:83mm:515.:
`
`
`
`
`
`
`
`mam—>52o.532Em_>m._m_>m:KEEP—.2museum
`
`$1.572
`
`3z..5qu
`
`Sim:
`
`GEN3mm22:32:28Em
`
`
`
`2.2328.5”5mmazEEwm._.__u_
`
`a2_$55.532
`
`
`
`OMEN—’523m:22:22:28Em
`
`2:;53m”5mum—222mm::
`
`
`
`a2_E5:.532
`
`EX 1008 Page 14
`
`EX 1008 Page 14
`
`
`
`
`
`
`
`

`

`US 6,633,564 B1
`
`1
`METHOD AND APPARATUS FOR
`INSERTING PACKETS INTO A DATA
`STREAM
`
`15
`
`2
`time of at least 76 usec (1 block) and as high as 684 usec (9
`blocks) for each packet. As a result, the jitter (or variability
`in arrival time) observed for speech or Video packets inter
`spersed with other large packets may fluctuate from 76 uSec
`to 684 uSec which leads to a Substantial degradation in
`performance.
`In conventional Systems, it is up to the Scheduler process
`in the transmitter to try to organize the transmission of the
`packets Such that the higher priority packets are not unduly
`delayed by other less important packets which have a lower
`priority. In So doing, the Scheduler must leave enough room
`on the communication link to allow for the transmission of
`higher priority packets when necessary. However, this often
`results in an inefficient use of the communication links
`which can also Seriously affect the overall performance of
`the communication network.
`In view of these problems, it would be desirable to be able
`to “interrupt” the transmission of an existing packet. AS
`noted above, there may be situations where Some packets are
`more important than others and may require transmission
`without being unduly delayed. This would occur where, for
`example, time Sensitive data Such as a speech packet must be
`transmitted while a long data packet is in the course of being
`transmitted. The Speech packet may be time Sensitive in the
`Sense that if it does not arrive in time at the receiver, there
`will be an audible interruption to the received speech. The
`longer data packet is typically of lower priority as it may be
`part of computer-to-computer communication in which a
`protocol such as the Transmission Control Protocol/Internet
`Protocol (TCP/IP) is being used to control the transport of a
`larger message composed of a number of packets which may
`arrive slowly (over an interval of a few milliseconds or
`Seconds) at the intended destination.
`Accordingly, there is a need to provide a communication
`network with an efficient method for interrupting the trans
`mission of existing (low-priority) packets to insert one or
`more new (higher priority) packets.
`SUMMARY OF THE INVENTION
`It is an object of the present invention to obviate or
`mitigate one or more of the above-identified disadvantages.
`For Systems in which packets are each transmitted as a
`Series of consecutive physical layer blocks, this invention
`provides a method and apparatus for efficiently interrupting
`the transmission of an existing packet to Send one or more
`interrupting packets which may have a higher priority than
`that of the existing packet. When an interrupting packet must
`be sent, the transmission of physical layer blocks used for
`the existing packet is interrupted to allow the transmission of
`at least one new block for the interrupting packet. The
`presence of the interrupting packet within the new block is
`efficiently denoted by existing fields which are already used
`for a different function when there is no interrupting packets.
`In a preferred embodiment, the invention is used in
`connection with common transmission Schemes known as
`the Data Over Cable Service Interchange Specification
`(DOCSIS) or the Asynchronous Transfer Mode (ATM)
`adaptation layer 2 (AAL2) format of the International Tele
`communications Union (ITU) recommendation I363.2. In
`these Schemes, the presence of a new packet in a physical
`layer block is indicated as part of the block format. In the
`DOCSIS specification, the presence of a new packet is
`indicated by a Payload Unit Start Indicator (PUSI) and a
`Pointer Field (PF). In the ATM AAL2 I.363.2 format, an
`OffSet Field (OSF) is used. The presence of an new inter
`rupting packet in a physical layer block is denoted by Setting
`
`25
`
`FIELD OF THE INVENTION
`This invention relates generally to the transmission of
`data in telecommunications networks and more particularly
`to the insertion of packets into an existing Stream of data.
`BACKGROUND ART
`In the vast majority of conventional communication
`networks, data is often arranged into packets So that it can
`be manipulated more easily. Packets are typically provided
`with Sufficient identification information to be handled inde
`pendently from one another. This identification information
`is usually contained in a header which is appended to each
`packet. With this information, packets generated by different
`users can be transmitted in any order and reassembled at the
`intended destination. This flexibility allows schedulers used
`in today's networks to interleave packets and concurrently
`Service transmission requests from different users.
`For the transmission of data packets in a communication
`network, it is often convenient to Subdivide each packet into
`smaller “chunks” known as physical layer blocks. By Sub
`dividing each data packet into Smaller physical layer blocks,
`the data packets can be more easily manipulated by the
`transmission equipment and coding techniques can be used
`to ensure their Safe transmission. For example, in order to
`ensure the error-free (low-error rate) transmission of data
`packets on a particular communication link, the packets may
`be subdivided into blocks and encoded with a forward error
`correcting code (FEC). Typically, this is done using a
`common block size as this allows the use of Standardized
`35
`encoding and decoding equipment at each end of the com
`munication link which is independent of the size of the data
`packets to be transmitted.
`While Some physical layer protocols allow physical layer
`blocks for different higher-protocol-layer packets to be
`interleaved, other physical layer protocols require the physi
`cal layer blocks to be transmitted consecutively for a given
`packet. This is the case, for example, where only the first
`physical layer block for a given packet contains information
`about the identity of the packet. In Such protocols an existing
`packet (or its associated blocks) cannot be “interrupted to
`transmit other packets which may have a priority higher than
`that of the packet in the process of being transmitted. AS the
`packets may be of varying size, depending of the user's
`application, high priority packets may be inappropriately
`delayed while waiting for long lower priority packets to
`complete their transmission.
`This problem is exacerbated if the packets are of widely
`varying Sizes. The presence of long user packets in the data
`Stream can Significantly increase the jitter or variation in the
`arrival time of other packets in the Stream and Seriously
`affect the overall performance.
`For example, in a commonly used transmission Scheme
`known as the ATSC A/53 Digital data/television standard,
`the user data is grouped into blocks of 188 bytes and
`transmitted at a rate of 10.7 mega-Symbols per Second or
`21.4 Megabits/second. Thus, the transmission of each block
`with this Standard requires approximately 76 micro-Seconds
`(pSec). User packets typically range from a few bytes to over
`1500 bytes, and in accordance with this particular Standard,
`may require anywhere from 1 to 9 blocks for transmission,
`depending on their length. This translates into a transmission
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`EX 1008 Page 15
`
`

`

`3
`the PUSI/PF or OSF to an unused value (and formely
`invalid) to flag the new packet as an interrupting packet.
`Advantageously, the method provided by the present
`invention can be practised recursively to accommodate
`multiple levels of interruption. AS Such, an interrupting
`packet can itself be interrupted by another, perhaps more
`important packet. When the transmission of an interrupting
`packet is complete, the transmission reverts back to the
`preceding level of interrupted packets until all levels of
`interruption are completed. With this method, multiple lev
`els of interruption may be realized to efficiently regulate the
`transmission of packets with different priorities.
`By comparison with existing methods, another advantage
`of the present invention is that the Scheduling of packets is
`Significantly simplified. Because data packets can be inter
`rupted whenever necessary, they can be transmitted anytime
`without delaying the transmission of higher priority packets.
`AS a result, the idle periods are reduced and the communi
`cation links present in a network are more efficiently used.
`Yet Still another advantage of the present invention is that
`the jitter in the arrival time of higher priority packets can be
`better controlled which results in a Significant improvement
`in transmission performance.
`Other aspects and features of the present invention will
`become apparent to those ordinarily skilled in the art upon
`review of the following description of Specific embodiments
`of the invention in conjunction with the accompanying
`figures.
`BRIEF DESCRIPTION OF THE DRAWINGS
`Preferred embodiments of the invention will now be
`described with reference to the attached drawings in which:
`FIG. 1 is a block diagram of a communications network
`and Subtending user equipment;
`FIG. 2 is a diagram of a data packet defined by the data
`over cable service interchange specification (DOCSIS)
`which is used to carry ISO8802 data packets in the network
`of FIG. 1;
`FIG. 3A is a diagram of a Motion Picture Experts Group
`(MPEG) block used for transmitting packets such as the
`ISO8802 data packet illustrated in FIG. 2;
`FIG. 3B is a diagram of an Asynchronous Transfer Mode
`(ATM) adaptation layer 2 (AAL2) cell defined by the
`International Telecommunications Union (ITU) recommen
`dation I363.2;
`FIG. 4 is a diagram of three MPEG blocks used for
`transmitting a longer packet;
`FIG. 5 is a diagram of an MPEG block showing the
`insertion of an interrupting packet into an existing packet of
`the data Stream according to an embodiment of the inven
`tion;
`FIG. 6 is a diagram of two MPEG blocks showing the
`insertion of an overlapping interrupting packet into an
`existing packet of the data Stream according to an embodi
`ment of the invention;
`FIG. 7 is a diagram of two MPEG blocks showing the
`insertion of an overlapping interrupting packet before a new
`packet of the data Stream according to an embodiment of the
`invention;
`FIG. 8 is a diagram of three MPEG blocks showing the
`insertion of three interrupting packets into an existing packet
`of the data Stream according to an embodiment of the
`invention;
`FIG. 9 is a diagram of two ATM cells showing the
`insertion of an overlapping interrupting packet into an
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,633,564 B1
`
`4
`existing packet of the data Stream according to another
`embodiment of the invention;
`FIG. 10 is a flow chart of a conventional Scheduler
`process used for packet transmission;
`FIG. 11A is a flow chart of a first portion of a block
`assembly algorithm for packet transmission according to the
`invention;
`FIG. 11B is a flow chart of a second portion of the block
`assembly algorithm of FIG. 11A;
`FIG. 11C is a flow chart of a third portion of the block
`assembly algorithm of FIG. 11A; and
`FIG. 11D is a flow chart of a fourth portion of the block
`assembly algorithm of FIG. 11A.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`This invention provides a network with a method to
`interrupt the transmission of an existing packet to insert one
`or more packets of a higher priority. The invention can be
`incorporated in any network topology or configuration. For
`simplicity however, the invention will now be described
`only in relation to a communications network (hereinafter
`referred to as “the network”). An example of a network is
`shown in FIG. 1 as generally indicated by 14.
`The network 14 illustrated therein is composed of a
`plurality of nodes indicated by 1, 2, 3, 4 (only four shown)
`Each of these network nodes 1, 2, 3, 4 is linked to others of
`the network nodes 1, 2, 3, 4 by one or more communication
`links X respectively 7, 8, 9, 10, 11.
`The network 14 is also interconnected with other net
`works 19 to provide network users with a variety of services
`Such as Internet-based Services, cable TV or access to the
`public Switched telephone network (PSTN). These services
`are remotely available to users by way of acceSS connections
`12, 13 (only two shown) to the nodes 1,2,3,4. As is the case
`with most network access connections, these connections
`12, 13 may be implemented with coaxial cables, telephone
`lines or alternatively implemented with radio. AS Such, the
`connections 12, 13 have a limited bandwidth and efficient
`use of them is quite important.
`FIG. 1 shows a typical connection arrangement for multi
`Service acceSS which consists of terminating each access
`connection 12, 13 by a respective set-top-box (STB) 105,
`106 with connections to a personal computer (PC) 5, 6 for
`access to Internet-based services, a telephone set 15, 17 for
`voice services and a television set 16, 18 for video services.
`The STBs 105, 106 are shown on FIG. 1 as stand-alone
`devices. It is understood that the STBs 105, 106 could
`alternatively be implemented within the PCs 5, 6 or in the
`further alternative, within any other device which can be
`modified to incorporate the STB functionality.
`The user information exchanged on either connection link
`12, 13 may consist of Voice, Video, data or a combination
`thereof, depending on which Services are operational. For
`example, a user at the PC 5 may connect to the network 14
`for downloading a file from an Internet Site and at the same
`time, talk on the phone 15 to another user on the phone 17
`also connected to the network 14 through the STB 106, in
`which case both data and voice information would be
`eXchanged on the communication link 12.
`In FIG. 1, each STB 105, 106 provides the necessary
`interface for the exchange of user information between the
`network 14 and the telephone sets 15, 17 for voice services,
`the television sets 16, 18 for video services and the service
`applications loaded in each PC 5, 6 (not shown) for
`
`EX 1008 Page 16
`
`

`

`US 6,633,564 B1
`
`15
`
`25
`
`35
`
`40
`
`S
`computer-based services. As such, the STBs 105,106 con
`Vert the user information received into a Suitable format and
`forward the converted information to the intended destina
`tion. For example, in the course of a telephone conversation
`between two users connected through the network 14 with
`the phones 15, 17, the speech information generated by the
`telephone set 15 which is intended for the other set 17 is first
`converted by the corresponding STB 105 into a format for
`transmission to the network 14 over the associated commu
`nication link 12. The converted information traverses the
`network 14 and reaches the other STB 106 where the
`information is converted back into a format Suitable for use
`by the other telephone Set 17. The same process also applies
`in respect to Speech information travelling from the tele
`phone set 17 to the set 15 and also to any other types of
`information travelling through the STBs 105, 106. The
`manner in which this information is converted by the STBs
`105, 106 is well-known in the art and is not described here
`in any detail.
`The user information exchanged between the STBs 105,
`106 and the network 14 is arranged in the form of packets
`which are each packaged with a header containing identifi
`cation information Such as the packet type and length. The
`packets are formatted according to the Data Over Cable
`Service Interchange Specification (DOCSIS). DOCSIS is a
`well-known transmission Scheme which is widely used to
`access networks for the exchange of multi-media informa
`tion as it has defined a number of different packet formats.
`These packet formats can be used for the transmission of
`Video or data.
`FIG. 2 shows as an example the format specified by the
`DOCSIS standard to carry an ISO8802 data packet. For
`Simplicity, the data packet shown in this figure is hereinafter
`referred to as a DOCSIS packet. The DOCSIS packet is only
`representative of a particular format specified by DOCSIS
`and it is to be noted that DOCSIS also specifies other
`formats to carry different types of data packets. It is to be
`understood in this description that by referring to a DOCSIS
`packet, reference to other formats is also implied.
`The format for the DOCSIS packet shown in FIG. 2 is
`formed of a payload 21 to contain the ISO8802 data packet
`and a six byte header 20. The ISO8802 data packet contained
`in the payload 21 is itself comprised of a destination address
`(DA) 22 specifying the address of the intended destination
`of the ISO8802 packet, a source address (SA) 23 specifying
`the Source address of the packet, a type/length field 24
`Specifying the type and length of the payload 21, the 0 to
`1500 bytes of user data 25 carried by the packet and a cyclic
`redundancy code (CRC) 26 which acts as an error detection
`code to detect the occurrence of transmission errors in the
`payload 21. The ISO8802 data packet in the payload 21 is
`used for carrying a portion of the user data to be transmitted
`and is packaged with the header 20 which contains a number
`of standard DOCSIS fields to properly identify the ISO8802
`packet and its contents. Of particular interest are the fields
`identifying the packet type 27 (ISO8802) and length 28
`which, for an ISO8802 packet, can range from 18 bytes (just
`the DA22, the SA 23, the type/length field 24 and the CRC
`26) to 1518 bytes (full length).
`For the transmission of packets such as the DOCSIS
`packet illustrated in FIG. 2, it is often convenient to block
`each packet into Smaller chunks known as physical layer
`blocks. By Subdividing each packet into Smaller blocks, the
`packets can be more easily manipulated by the transmission
`equipment. Moreover, coding techniques can be used to
`improve the reliability of the transmission and enhance
`performance. For example, in order to reliably transmit data
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`packets between the STB 105 and node 4 of the network 14
`over the communication link 12 (see FIG. 1), the packets are
`first Subdivided into blocks and then are encoded with a
`forward error correcting code (FEC). Typically, this is done
`using a common block size as this allows the use of
`Standardized encoding and decoding equipment at each end
`of the communication link 12 which is independent of the
`Size of the data packets to be transmitted.
`An example of this is the DOCSIS transmission of data or
`video information between the STBs 105, 106 and the
`network 14. For this, DOCSIS specifies a common block
`size of 188 bytes. As is well known, the 188 byte block size
`Specified was Selected to be compatible with a common
`video image coding scheme developed by the Motion Pic
`ture Experts Group (MPEG) so that the encoding and
`decoding of the physical layer blockS could be standardized.
`The physical layer blocks formatted in accordance with the
`MPEG standard are commonly referred to as MPEG physi
`cal layer blocks or simply MPEG blocks.
`As noted above, the common block size of 188 bytes
`defined by DOCSIS for the transmission of data or video
`packets permits the use of Standard coding techniques to
`improve the reliability of transmission. Accordingly, the
`MPEG blocks used for the transmission of DOCSIS packets
`between the STBs 105,106 and the network 14 are encoded
`with a FEC referred to as the Reed Solomon (RS) code
`(188,204). The RS coding scheme encodes the 188-byte
`block to a physical layer block of 204 bytes with the ability
`to correct up to 10 bytes of errors in transmission. To further
`describe the format of the MPEG blocks used for transmit
`ting DOCSIS packets, reference is now made to FIG. 3A
`which shows, as an example, the format of an MPEG
`physical layer block encoded with the RS code (188,204).
`The MPEG physical layer block shown therein is com
`prised of a data payload 30 for carrying DOCSIS packets or
`a portion thereof, a 16 byte RS-FEC code 31 for correcting
`potential transmission errors and an optional pointer field 32
`to identify the beginning of each included DOCSIS packet
`(further details below). According to the MPEG standard,
`the optional pointer field 32 uses one byte and the data
`payload 30 is 183 or 184 bytes long, depending on whether
`or not the pointer field 32 is present in the MPEG block to
`signify the beginning of a new DOCSIS packet (further
`details below). The MPEG block is packaged with a 4 byte
`header 33 which mainly serves to mark the block's bound
`aries and control its transmission.
`As is well known, DOCSIS packets are of varying sizes
`and do not fit perfectly into the fixed length MPEG block
`size. As such, the transmission of a DOCSIS packet may
`require several MPEG blocks or alternatively, one MPEG
`block may be sufficient to transmit several DOCSIS packets.
`As multiple MPEG blocks can be used to transmit a DOC
`SIS packet or alternatively, as a single MPEG block can be
`used to transmit several DOCSIS packets, it becomes desir
`able for a receiver used in the network 14 or in either the
`network or one of the STBs 105, 106 (see FIG. 1) to have
`the ability to locate the beginning of every DOCSIS packet
`received for the purpose of reassembly and processing. If
`there were no errors in transmission, the receiver might
`choose to find any DOCSIS packet by decoding all the
`incoming packets from the MPEG physical layer blocks and
`watching their length fields. AS was described above, these
`length indicators show the length of the DOCSIS packets,
`and hence may be used to find the Starting place of the next
`packet in an incoming Stream of data.
`However, if there are errors in transmission or one of the
`MPEG physical layer data blocks is lost, the receiver will be
`
`EX 1008 Page 17
`
`

`

`US 6,633,564 B1
`
`15
`
`7
`unable to find the beginning of the next DOCSIS packet as
`it re-synchronizes itself to correctly receive and decode the
`MPEG physical layer blocks. The DOCSIS packet headers
`are generally indistinguishable in the data Stream from the
`data they carry and thus cannot easily be found by Simply
`looking at the data Stream. Some data transmission Systems
`make use of a packet header that is distinguishable from the
`data, but doing So is inefficient and Substantially reduces the
`number of possible data patterns for transport and, as a
`result, is not the preferred method for this application.
`In order to identify the beginning of each DOCSIS packet
`transmitted, the MPEG block is packaged with the optional
`pointer field 32 and a payload unit start indicator (PUSI) bit
`34 which is contained in the header 33. In addition to the
`PUSI 34, the MPEG header 33 also includes synchroniza
`tion fields (not shown) and information relating to Service
`identification and transport priority (not shown). This addi
`tional data contained in the MPEG header 33 is well-known
`in the art and is not be described here in any detail.
`According to the DOCSIS standard, the begining of
`DOCSIS packets may be placed anywhere within the pay
`load 30. While at the beginning of a transmission, the first
`MPEG block sent will typically coincide with the start of the
`first DOCSIS packet to be transmitted, after a few MPEG
`25
`blocks and with a mixture of sizes of DOCSIS packets, there
`is no fixed relation between the MPEG physical layer block
`boundaries and the DOCSIS packets. That is, for any given
`MPEG block, a DOCSIS packet (and its corresponding
`header) may start anywhere within the payload 30 portion
`and, as a result, may overlap the block boundaries to extend
`into Subsequent MPEG blocks.
`As noted above, the PUSI bit 34 is part of the MPEG
`block header 33. If the PUSI bit 34 is set, it indicates that the
`MPEG block contains the start of a DOCSIS packet, and that
`the first byte after the MPEG header 33 contains a pointer
`(the pointer field 32) to the beginning of the DOCSIS packet.
`In between the pointer field 32 and the beginning of the
`DOCSIS packet, there may be either the tail end of a
`previous DOCSIS packet, or in some cases, some fill
`40
`(unused) bytes. As such, a receiver may examine the MPEG
`block header 33 and learn where the next DOCSIS packet
`starts within the MPEG block. If the PUSI bit 34 is not set,
`it indicates that the payload 30 is the continuation of a packet
`Started in a previous block and that this continuation fills this
`45
`entire block. In this way, the variable sized DOCSIS packets
`can be efficiently placed into the standard size MPEG
`physical layer blockS.
`According to the MPEG standard, the pointer field 32 is
`one byte. AS Such, the pointer field 32 may accomodate
`numbers in the range 0 to 255. The maximum payload size
`in the MPEG block is 183 bytes, which leaves the pointer
`field values from 184 to 255 unused.
`The Asynchonous Transfer Mode (ATM) adaptation layer
`2 (AAL2) format of the International Telecommunications
`Union (ITU) recommendations I363.2 makes us