(12) United States Patent
`Olsson et al.
`
`USOO6577596B1
`US 6,577,596 B1
`Jun. 10, 2003
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR PACKET
`DELAY REDUCTION USING SCHEDULING
`AND HEADER COMPRESSION
`
`(75) Inventors: Gunnar Olsson, Tumba (SE); Simon
`Rahlén, Tullinge (SE)
`(73) Assignee: Telefonaktiebolaget LN Ericsson
`(publ), Stockholm (SE)
`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/451,081
`(22) Filed:
`Nov.30, 1999
`(51) Int. Cl." ................................................ H04L 12/26
`(52) U.S. Cl. ................................... 370/230; 370/395.42
`(58) Field of Search ................................. 370/229, 230,
`370/230.1, 231,395.4, 395.41, 395.42,
`395.43, 428,429, 412, 413, 415, 417, 468,
`477
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,231,633 A * 7/1993 Hluchy et al. ............. 370/429
`5,293,379 A
`3/1994 Carr
`5,978,386 A 11/1999 Hämäläinen et al.
`5.987,022 A 11/1999 Geiger et al.
`5.999,528 A * 12/1999 Chow et al. ................ 370/365
`6.269,079 B1 * 7/2001 Marin et al. ...
`... 370/230
`6,324,165 B1
`11/2001 Fan et al. ................... 370/232
`6,449.255 B1 * 9/2002 Waclawsky ................. 370/236
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`99/13624
`
`3/1999
`
`OTHER PUBLICATIONS
`W. Storz and G. Beling “Transmitting time-critical data over
`heterogeneous Subnetworks using Standardized protocols',
`Mobile Networks and Applicatiosn 2 (1997) pp. 243-249,
`document No. XP-000853528.
`
`“Open Systems Interconnect (OSI)-New International
`Standards Architectures and Protocols for Distributed Infor
`mation Systems”, Special issue, Proceedings of the IEEE,
`H.C. Folts and R. des Jardins, eds., vol. 71, No. 12, Dec.
`1983.
`“Internet Protocol Specification’, E.J. Postel, SRI Interna
`tional, Menlo Park, CA, Sep. 1981, RFC791.
`“The Point to Point Protocol" editor W. Simpson, Network
`ing Group Request for Comments RFC 1661, Jul. 1994.
`“Cisco IOSTM Software Quality of Service Solutions”, Apr.
`8, 1999, by Cisco Systems.
`“Multi-Class Extension to Multi-Link PPP, Carsten Bor
`man, Internet Engineering Task Force (IETF), Dec. 1999.
`“Providing Integrated Services Over Low-bitrate Links”, by
`Carsten Borman, Jun. 1999.
`“Compressing TCP/IP Headers for Low-Speed Serial
`Links”, editor V. Jacobson, Feb. 1990.
`* cited by examiner
`Primary Examiner Kwang Bin Yao
`(57)
`ABSTRACT
`A method and apparatus for reducing delay in the transmis
`Sion of a plurality of packets by performing IP Scheduling
`and header compression at various layers in a multilayer
`architecture having a plurality of classifications includes
`Scheduling packets according to classifications. If conges
`tion occurs during Scheduling, packets may be discarded.
`Some packet headers may be compressed thereafter. Packets
`may further be queued in a first and a second queue, after
`Scheduling, discarding, and compressing, according to at
`least two classifications. Best Efforts packets may be queued
`into the lower priority Second queue. Classifications may be
`asSociated with, for example, QoS levels, delay factors, LFI,
`and Multilink PPP. Scheduling is performed at higher or
`lower layers in a multi-layer protocol. The lower layer
`includes a PPP layer. The lower layer may also include an
`HDLC layer which creates a tag for packets prior to com
`pression being performed thereupon. The tag may be added
`to packets at Some point thereafter. Tags are removed prior
`to transmission. An outbound packet queue having a queue
`depth of no greater than one ensures no more than one Best
`Efforts packet wait time.
`23 Claims, 8 Drawing Sheets
`
`
`
`
`
`
`
`Afip
`AA
`Apass.
`
`ASA:
`AAEf
`
`-552
`
`Af
`AAA
`iPassi:
`
`582
`
`
`
`
`
`AB 2, 2, ...,ty
`pais F.
`A. App
`
`563
`
`
`
`55
`
`552d
`
`Stifs
`ApAffisii
`Aaaaiii
`Affilia AAA
`
`P
`falafi 9ts
`Atti,
`A.
`
`AAESS Flais FApp -553
`
`557
`
`i, 20ftf
`
`
`
`555
`
`2 taif
`Apr.
`
`556
`
`A
`
`Bita
`-;
`ipf2
`
`it
`At
`564 - AAFS
`Appa
`
`
`
`Aft
`
`Appi Atar
`is App
`
`
`
`AF
`Af
`PS
`
`EX 1009 Page 1
`
`

`

`U.S. Patent
`
`Jun. 10, 2003
`
`Sheet 1 of 8
`
`US 6,577,596 B1
`
`A/G f
`
`93b
`193C
`
`93d
`93e
`
`93f
`193g
`
`
`
`193C
`
`
`
`artz o.
`f :
`
`as a viv -193
`It
`(OWWAA/70//WAAA ()
`-194
`
`/A (AZAS//
`
`95
`
`2
`y
`4
`
`-93h
`(WPGAA/WA0/W/AA (W)
`–93;
`r a wov ()
`-193k
`--- 4 Acr (a)
`4 stovsc, (s)-93.
`---A p in ()|-193m
`
`- - - - - - - - - - - - - - - - - - - - - - -
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`EX 1009 Page 2
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 10, 2003
`Jun. 10, 2003
`
`Sheet 2 of 8
`Sheet 2 0f 8
`
`US 6,577,596 B1
`US 6,577,596 B1
`
`Off?
`SN
`
`com
`
`
`
`27 59/-/
`
`35£538N65K
`
`2N
`
`EX 1009 Page 3
`
`EX 1009 Page 3
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 10, 2003
`Jun. 10, 2003
`
`Sheet 3 of 8
`Sheet 3 0f 8
`
`US 6,577,596 B1
`US 6,577,596 B1
`
`
`
`
`
`§
`
`£2
`
`m,“9K
`2° 0/-/
`
`EX 1009 Page 4
`
`EX 1009 Page 4
`
`
`
`

`

`U.S. Patent
`
`Jun. 10, 2003
`
`Sheet 4 of 8
`
`US 6,577,596 B1
`
`40
`
`420
`
`
`
`O
`43
`
`440
`AAF () ()
`
`450
`
`-- peopoa II so
`
`460
`
`43
`
`
`
`432
`
`AAFWF (A/A
`
`A/G 44
`
`460
`
`even
`
`460
`
`A f (IASS 450
`430
`--
`
`pore pasto a an on
`
`N--
`4
`
`480
`
`470
`
`
`
`
`
`
`
`
`
`
`
`410
`
`420
`
`a
`
`460
`
`40
`
`420
`
`460
`
`A/G 4A
`
`Yo
`
`430
`
`0/ASS
`AAF
`MM
`
`450
`
`-- peopoa II score
`
`N--
`442
`460
`
`470
`
`400
`
`APA/AWW (A/A
`
`AAAAAW MJA
`
`A/G 4C
`
`EX 1009 Page 5
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 10, 2003
`Jun. 10, 2003
`
`Sheet 5 0f 8
`Sheet 5 of 8
`
`US 6,577,596 B1
`US 6,577,596 B1
`
`
`
`\l
`V:
`0,79
`3w:
`u:
`E
`
`7%)/6/////
`
`R
`
`%
`
`OOI
`
`009
`
`!)
`
`§_%
`§
`LO
`
`0
`K
`3““g
`
`[‘3
`Q5
`L?
`
`3S
`VMSB
`\l
`U")
`
`|
`
`511
`
`512
`
`515
`
`514
`
`EX 1009 Page 6
`
`EX 1009 Page 6
`
`

`

`US. Patent
`
`Jun. 10, 2003
`
`Sheet 6 0f 8
`
`US 6,577,596 B1
`
`EE§Q
`
`-5%«xx&§§§£2$33
`
`3%:..@é§
`
`
`
`EEKKb§§Sm.3:588
`
`«3E
`
`&Q33%fi§§§§
`
`KKKKKKK
`
`KKKEK
`
`KKQQKKKS»
`
`xx”KmE
`
`«$th
`
`§$K$$wSKKKuw
`
`%E3KEKV3%quKK
`
`KKKIEEEEGVK
`
`t§¢§§
`
`
`
`KKKI3.3KKKKK“5%qumwKuKKK
`
`‘KKKKKK
`
`KKKRVK
`
`KKRQKKKKK
`
`
`
`KKKSK
`
`w2%$§
`
`§§\K
`
`NEE
`
`mm“9K
`
`NEE
`
`5%\é
`
`awnK.NSK
`
`KKKIa.
`
`NEE
`
`“ERé
`
`MESé
`NEE
`
`EX 1009 Page 7
`
`EX 1009 Page 7
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 10, 2003
`Jun. 10, 2003
`
`Sheet 7 of 8
`Sheet 7 0f 8
`
`US 6,577,596 B1
`US 6,577,596 B1
`
`
`
`S.
`540
`
`3.
`600
`
`s
`F/G.6
`
` PHYS/6,41
`
`EX 1009 Page 8
`
`EX 1009 Page 8
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 10,2003
`Jun. 10, 2003
`
`Sheet 8 0f8
`Sheet 8 of 8
`
`US 6,577,596 B1
`US 6,577,596 B1
`
`541
`
`2
`CNU
`
`1
`y
`
`s
`1000
`/ 3 Sr:
`s is
`s
`\-A
`/
`”—
`V
`I
`
`s
`F/G.7,4
`
`
`
`s s
`”,7=55
`
`”AI—I
`
`E
`711
`
`ic
`611
`
`S
`723
`
`S.
`724
`
`WW
`WN-.x
`
`S
`‘1‘
`S C
`¥__$
`SS S Q
`§
`10
`K
`
`o
`E
`§‘—f&‘
`
`S C s-s
`
`F76373
`
`7346'
`
`s
`752
`
`e
`751
`
`e
`750
`
`o
`K
`3:“:
`
`O
`$““25
`
`EX 1009 Page 9
`
`EX 1009 Page 9
`
`

`

`US 6,577596 B1
`
`1
`METHOD AND APPARATUS FOR PACKET
`DELAY REDUCTION USING SCHEDULING
`AND HEADER COMPRESSION
`
`BACKGROUND
`The present invention relates to multiplex communication
`Systems for transferring information in packets and more
`particularly, to Scheduling and header compression of pack
`ets in a multilayered network architecture.
`Modern communications networks carry increasing
`amounts of packet traffic which is associated with real-time
`Voice, Video, and related data. The Internet, for example, is
`Seeing many new applications which take advantage of what
`is a relatively less costly alternative to conventional tele
`phone call connections for Sending a variety of data includ
`ing real time Voice and Video. Trends toward real time
`applications over the Internet are driven in part by increas
`ingly powerful computers being installed in private homes
`and the proliferation of the Internet as a focal point for
`Various on-line activities Such as holding voice
`conversations, listening to music, watching video clips, and
`the like. Unlike Internet communications which occur
`between computers on high bandwidth commercial
`connections, bandwidth in a typical home is limited by
`connectivity constraints imposed by modem Speed, line
`quality, and the like.
`Further compounding the basic problem of limited
`bandwidth, is the limitation on the amount of actual infor
`mation transmitted as a result of packet Overhead due to
`protocol headers. Basic Internet protocols were developed
`primarily for making Sure that packets were delivered accu
`rately end to end at a time when little consideration was paid
`to real time issues.
`Three layer interface architectures including protocols
`Such as X.25, for example, were developed for controlling
`transfer at the lower levels while higher layer protocols were
`developed to control more Sophisticated functions (see,
`“Open Systems Interconnect (OSI)-New International
`Standards Architectures and Protocols for Distributed Infor
`mation Systems,” special issue, Proceedings of the IEEE, H.
`C. Folts and R. des Jardins, eds., vol. 71, no. 12, December
`1983). According to the design philosophy, lower layer
`functions were contemplated to be “transparent to higher
`layer functionality and thus much of what can be accom
`plished at the lower layers is limited only by the ability of
`lower layer hardware and Software to preserve that trans
`parency. At the lowest layer, the Physical Layer, a protocol
`Specification governs the physical connection between
`devices, Such as, for example, the X.21 protocol. Next, the
`Data Link Layer Specifies the protocol for, for example,
`accepting packets from higher layerS and placing them into,
`for example, HDLC frames for transfer across the Physical
`Layer. The Data Link layer further may accept framed
`information from the Physical Layer and unpack it for
`transfer up to the Network Layer. At the Network Layer, or
`packet layer, multiple logical connections may be estab
`lished and addresses attached to packets based on Several
`assumptions including that Successful end to end delivery is
`not guaranteed, that orderly delivery is not guaranteed, and
`that packets or "datagrams' are delivered one at a time each
`containing information Such as destination address, and the
`like.
`It is important to note that while various lower layers are
`discussed herein, datagrams from higher layerS may form
`the input to a Network Layer proceSS or System, which in
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`turn provide input to Successively lower layers, and even
`tually to the destination. Higher layer datagrams input to a
`Network Layer entity may be input from, for example, a
`Transport Layer process or System. A typical and well know
`transport layer protocol is the Transport Control Protocol
`(TCP) although other Transport Layer protocols are known
`and used. In particular, the User Datagram Protocol (UDP)
`may often be used as a Transport Layer protocol. UDP is a
`protocol which defines a connectionless datagram Service. A
`Transport Layer process or System implementing UDP may
`produce Self-contained data packets which include destina
`tion routing information.
`A ubiquitous protocol for Network Layer communica
`tions over the Internet is the Internet Protocol (IP). The IP
`Specification includes an enumeration of fields associated
`with the IP header which fields contain information about an
`asSociated packet including information for determining
`how the packet should be delivered. The IP header fields will
`be described in greater detail herein below. For a more
`complete understanding of the contents of the IP header, See
`“Internet Protocol Specification”, E. J. Postel, SRI
`International, Menlo Park, Calif., September 1981, RFC791.
`For Data Link Layer communications, Point-to-Point
`Protocol (PPP) has become a dominant protocol. PPP
`includes three main components: a method of encapsulating
`multi-protocol datagrams, a datagram being a unit of trans
`mission in the network layer (Such as IP), a link control
`protocol (LCP) for establishing, configuring and testing the
`data-link connection, and a family of network control pro
`tocols (NCP) for establishing and configuring different
`network-layer protocols.
`PPP is designed to transport packets between two
`So-called peers, i.e. the two ends of a link conforming to the
`protocol. Accordingly, the LCP may be used to agree upon
`the encapsulation format options, handle varying limits on
`sizes of packets, detect configuration errors, and terminate
`the link. Other optional facilities are the authentication of the
`identity of its peer on the link, and the determination when
`a link is functioning properly and when it is failing. PPP
`linkS-provide full-duplex Simultaneous bidirectional opera
`tion. A definition of PPP may be found in the Networking
`Group Request for Comments RFC 1661, “The Point to
`Point Protocol” editor W. Simpson, July 1994.
`Communication across a link established using PPP is
`accomplished Such that a datagram associated with a pro
`tocol may be encapsulated into one or more frames. A frame,
`as described above, may include a header and/or a trailer,
`along with Some number of units of data. However, it is
`conventional that an entire packet is mapped into a frame.
`Conventional framing breaks down however during condi
`tions of heavy network congestion where fragmentation
`methods may be used to improve flow control management.
`Such congestion has arisen due to, among other factors, the
`increase in traffic caused by increased numbers of greater
`bandwidth connections provided by, for example, multilink
`service. Since both basic and primary rate ISDN, for
`example, allow for multiple Simultaneous channels between
`Systems to allow for bandwidth on demand, problems asso
`ciated with Such Services must be addressed. Congestion
`giving rise to latency may be a particular problem for real
`time data Such as voice or video, VoIP. Telnet, and the like.
`Such real time data formats have little or no tolerance to
`packet latency, jitter, packet reordering and related prob
`lems. Problems associated with the multilink environment
`only amplify the unique real time packet data requirements.
`To ease congestion in the multilink environment, one
`Solution known as Link Fragmentation and Interleaving
`
`EX 1009 Page 10
`
`

`

`US 6,577596 B1
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`15
`
`3
`(LFI) is proposed in the White Paper entitled “Cisco IOSTM
`Software Quality of Service Solutions”, Apr. 8, 1999, by
`Cisco Systems. In LFI, delay and jitter are reduced by
`breaking up large datagrams and interleaving time Sensitive
`packets with the resulting packet fragments. LFI is contem
`plated for relatively low speed links where Serialization
`delay is the predominant delay factor. LFI Simply requires
`that PPP be configured to allow for interleaving. Otherwise,
`LFI is transparent to PPP.
`A similar Solution is proposed in Internet Engineering
`Task Force (IETF), INTERNET-DRAFT, “Multi-Class
`Extension to Multi-Link PPP”, June 1999, expires: Decem
`ber 1999, by Carsten Borman. Here, a fragment oriented
`Solution may be found for the real time encapsulation of
`format which is part of the standard architecture of, for
`example, integrated Services communications linkS.
`Certain problems associated with conventional LFI,
`multi-link PPP, and related data transfer may best be illus
`trated by an example. The transfer of a 1.5 kbyte packet on
`a 28.8 kbit/s modem link may occupy the link, making it
`unavailable for data transfer of packets associated with other
`links in the multi-link environment, for upwards of 400 ms.
`Such delay may create round trip delays associated with
`interactive real time data, Such as a Voice conversation, of
`close to a Second. By fragmenting packets of various pri
`orities larger than a predetermined size high priority packets
`or fragments thereof may be sent between fragments of
`lower priority packets. Existing multi-link PPP specifica
`tions already provide for fragmentation by providing
`sequence numbers and begin and end bits in the PPP
`encapsulation format. However, existing multi-link PPP
`does not provide for the Suspension of transfer of fragments
`of one packet in order to Send another, due to contiguous
`packet numbering Schemes. The Solution proposed by
`Borman, Supra, includes running multiple multi-link proto
`col instances on the same link allowing for nesting of
`multiple Suspendable classes using unused bits in the multi
`link PPP protocol to specify class numbers. Accordingly,
`fragments belonging to a particular class can be sent without
`the multi-link header and four to twelve levels of suspension
`may be achieved depending on the number of header bits.
`Regardless of the methods of Scheduling fragments
`contemplated, problems arise in implementation. In
`particular, it should be noted that the lower three protocol
`layerS and associated protocols including, for example,
`UDP, IP, and PPP, along with the physical layer typically
`reside on hardware resources, Such as routers, which may
`introduce limitations that are detrimental to the benefits
`gained from fragmentation and other Scheduling methods. In
`particular, a router, for example, may typically queue out
`bound packets together in the same transmit queue once
`priority or the like has been established. The configuration of
`a typical outbound packet queue is generally First In First
`Out (FIFO) and has a level of intrinsic delay associated with
`the queue depth. Further, a router experiencing high traffic
`levels and using a typical outbound packet queue raises the
`possibility of packet dropping when congestion occurs, even
`when using LFI, multi-link PPP or the like. If packets are
`forced to be dropped from downstream queues after IP
`Scheduling occurs, problems related to packets received out
`of Sequence may occur. Depending on the link configuration,
`request for retransmission of the missing packets, for
`example, may cause delay and degradation of real time data.
`Packet dropping can be particularly troubleSome when
`used in conjunction with other methods of reducing con
`65
`gestion Such as, for example, header compression. By com
`pressing or discarding certain portions of information con
`
`4
`tained in a typical header, header compression methods
`reduce the Overall size of the datagram or packet. This is
`particularly important in the case of Small packets typically
`used for real time data transfer applications where the header
`may represent close to 100% packet overhead. Although,
`header compression may be performed at various Stages,
`problems arise due to an assumption which must be made in
`the art when using header compression that packet reorder
`ing or resequencing, including the effects of packet
`dropping, will not occur. Approaches for dealing with this
`problem adds nearly as much header overhead as was Saved
`originally with header compression techniques. For more
`general information on header compression See Internet
`Engineering Task Force (IETF), INTERNET-DRAFT, “Pro
`viding Integrated Services Over Low-bitrate Links”, June
`1999, expires: December 1999, by Carsten Borman, and see
`also Networking Group Request for Comments RFC 1144,
`“Compressing TCP/IP Headers for Low-Speed Serial
`Links”, editor V. Jacobson, February 1990.
`On Slow links, as described, time Sensitive packets can not
`afford to wait for the completion of, for example a long Best
`Efforts (BE) data packet. Using IP fragmentation may
`improve latency for Such packets, but at a cost of adding a
`header of around 20 bytes for each Segment. Another Solu
`tion is to use Multi-link PPP segmentation that adds a header
`of 2 or 4 bytes to each Segment. Such headers are designed
`to propagate Scheduling information to the Segments or
`fragments. Header compression, however, makes IP Sched
`uling difficult. When header compression is used, informa
`tion including the identification field in the IP header
`becomes unavailable to lower layers after compression. If a
`HC packet is dropped, the resulting missing Sequence num
`ber at the receiver will cause problems on the link, as
`previously described, Since the receiver will, for example,
`request retransmission of the dropped packet and the layer
`responsible will be unable to identify which packet was
`dropped and will thus be unable to request the dropped
`packet from higher layers, introducing further delay and
`degradation of quality.
`Therefore, it would be appreciated in the art for a method
`and apparatus which handles Scheduling and reduces the
`adverse effects on Scheduling imposed by header compres
`Sion on dropped packets. Such a method and apparatus
`would operate without disruption of the operation of the IP
`layer allowing generic IPScheduling on pure IP packets with
`header compression.
`
`SUMMARY
`It is therefore an object of the present invention to provide
`a method and apparatus for reducing packet delay using
`Scheduling and header compression.
`It is a further object of the present invention to provide
`Such a method and apparatus at various layers within a
`multi-layer protocol implementation.
`Therefore, in accordance with one aspect of the present
`invention, the foregoing and other objects are achieved in a
`method and apparatus for reducing delay in the transmission
`of a plurality of packets. The packets may have a plurality
`of classifications according to a multi-layer protocol having
`at least a higher layer, and a lower layer. Packets may be
`Scheduled according the associated classifications. If con
`gestion occurs during Scheduling, packets which cannot be
`Scheduled may be discarded. After Scheduling and discard
`ing Some packet headers may be compressed and,
`accordingly, Sequence information may be preserved.
`In accordance with another embodiment of the present
`invention, packets may be queued in a first and a Second
`
`EX 1009 Page 11
`
`

`

`S
`queue, after Scheduling, discarding, and compressing,
`according to at least two of the plurality of classifications,
`the first queue having priority over the Second queue. For
`example, one the two possible classifications may include
`Best Efforts classification Such that queuing would include
`determining whether packets are classified as Best Efforts
`packet and if So, queuing Best Efforts packets into, for
`example, the Second queue.
`It should be understood that a number of classifications
`may be included which may be associated with, for example,
`QoS levels as may be found in an IP header associated with
`a packet. Classifications may also be associated with a
`plurality of delay factors and it may be preferable to estab
`lish a plurality of queues based on the plurality of classifi
`cations. Accordingly, each packet may be queued into one of
`the plurality of queues based on an associated classification.
`In accordance with yet another embodiment of the present
`invention, the plurality of classification may be associated
`with Link Fragmentation and Interleaving (LFI) as described
`herein above. Alternatively, the plurality of classifications
`may be associated with Multilink PPP as also described
`herein above.
`It should further be noted that in accordance with the
`present invention, Scheduling may be performed at the
`higher or lower layers, wherein the lower layer may include
`a PPP layer as described above. The lower layer may further
`include an HDLC layer and when scheduling is performed
`therein, a tag may be created for each of the packets prior to
`header compression. The tag may be added thereafter and
`may be removed prior to transmitting. Each packet from the
`first and the Second queue may be queued in an outbound
`packet queue having a queue depth of no greater than one.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The objects and advantages of the invention will be
`understood by reading the following detailed description in
`conjunction with the drawings, in which:
`FIG. 1 is a diagram illustrating an exemplary compressed
`datagram and format using TCP/IP;
`FIG. 2 is a diagram illustrating exemplary Link Fragmen
`tation and Interleaving;
`FIG. 3 is a diagram illustrating exemplary priority queu
`Ing,
`FIG. 4A is a diagram illustrating an exemplary fragmen
`tation format for multilink PPP;
`FIG. 4B is a diagram illustrating an exemplary fragmen
`tation format accommodating multiple classes and short
`sequence numbers for multilink PPP;
`FIG. 4C is a diagram illustrating an exemplary fragmen
`tation format accommodating multiple classes and long
`sequence numbers for multilink PPP;
`FIG. 5A is a diagram illustrating exemplary pure IP
`Scheduling in accordance with the present invention;
`FIG. 5B is a flowchart illustrating exemplary pure IP
`Scheduling in accordance with the present invention;
`FIG. 6 is a diagram illustrating exemplary IPScheduling
`at the PPP layer in accordance with the present invention;
`FIG. 7A is a diagram illustrating exemplary IPScheduling
`at the HDLC layer in accordance with the present invention;
`and
`FIG. 7B is a diagram illustrating exemplary tag attached
`to a compressed header at the HDLC layer in accordance
`with the present invention.
`DETAILED DESCRIPTION
`Therefore in accordance with the present invention a
`method and apparatus are provided which allow header
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,577596 B1
`
`6
`compression to be used in conjunction with IPScheduling at
`various layers in a network node Such as a router, line
`interface card, or the like.
`It should be noted that in accordance with the present
`invention, header compression of IP packets may be per
`formed as described herein at various Stages according to
`particular embodiments of the present invention. An exem
`plary compressed header format is illustrated in FIG. 1
`which might result from, for example, a header compression
`operation on a typical TCP/IP header. As was previously
`noted, TCP is used herein to exemplify a transport layer
`protocol although other transport layer protocols, preferably
`UDP, may also be used in accordance with the present
`invention. AS can be seen, important information may be
`carried over into the compressed packet and may be inter
`preted through processing of, for example, change mask 193
`which indicates which of the fields expected to change
`actually change. Bits 193a–193g may be used to indicate
`these changes as the compressed header format may typi
`cally be made up of the fields which are expected to change
`during the course of a connection or packet Session. Con
`nection number field 194 may contain a value which allows
`a receiver to locate a Saved copy of the last packet from the
`particular connection indicated for the purposes of compar
`ing the previous value of, for example, change mask 193
`with its present value. TCP checksum field 195 contains a
`checksum for the compressed header calculated in a manner
`known in the art. Urgent pointer 193h contains a value
`pointing to urgent data. The remaining fields represent
`changes in the values for the associated fields, for example,
`A window field 193j represents the change in window field
`and thus may be represented using a Smaller value reducing
`the size of the field from two octets to one. Likewise, A ack
`field 193k, represents the change in acknowledgment num
`ber field and uses one octet instead of four. A sequence field
`193l represents the change in Sequence number field and,
`again, results in a reduction from four octets to one. A IP ID
`field 193m represents the change in Packet ID field from an
`asSociated IP header and may result in a reduction in size
`from two octets to one. Finally data field 196 may follow at
`the end of compressed header fields as shown. It should be
`noted that in the case where, for example, no changes are
`present between packets, fields 193h-193m may be omitted
`and data field 196 may follow directly behind TCP check
`Sum field 195. It should be noted that the above mentioned
`fields may be associated with an exemplary IP packet with
`header compression performed thereon. It may further be
`possible to reduce the number of fields compressed or to
`compress an incoming IP packet and Simply include a tag in
`accordance with the teachings of the present invention.
`With an understanding of the fundamental nature of
`multilayer protocols, it is possible to appreciate the prob
`lems associated with congestion control in links carrying
`multiple data types, (e.g. real time, Best Efforts, and the like)
`which may be header compressed. These problems are
`particularly troublesome at layers below the layer which
`header compression occurred on especially when packets are
`Scheduled prior to header compression and then discarded
`due to congestion after compression has been performed.
`During periods of congestion it is often the case that packets
`awaiting transfer must be Scheduled or queued using Several
`known methods. FIG. 2 illustrates an exemplary network
`node 200 using a typical network Service Stack having the
`lower three layers. Exemplary data packets 211, 212, and
`213 are shown entering network layer 210, where process
`215 may decide based on the time sensitivity, shown, for
`example with reference to packet 212 as D, with D
`
`EX 1009 Page 12
`
`

`

`7
`indicating the highest time Sensitivity and D indicating a
`relatively lower time Sensitivity, where to position incoming
`packets for transfer within queues 221, 222, 223, 224 of
`Link Fragmentation and Interleaving (LFI) layer 220. It can
`be seen that LFI layer 220 may occupy at least a portion of
`data link layer 230. Packets in queue D 224 may be sent
`first, then D 223, D 222, and D 221. Long packets Such
`as represented by packet 213 may be fragmented into
`Smaller packets as represented by packetS 213a, 213b, and
`213d. AS long packets are generally of a lower priority, high
`priority packets associated more often with real time data
`Such as voice, audio, or Video, Such as represented by
`packets 214a, 214b, and 214c may be accumulated prior to
`transfer in queue 224. AS packets enter queues 221-224 they
`are transferred to the physical layer by process 231 which
`may be a typical data link proceSS Such as HDLC or the like
`where they can be processed in FIFO transmit queue 232 and
`output to physical link 233.
`Notwithstanding LFI methods as described above, once
`packets are fragmented, they may be queued according to,
`for example, a conventional priority queuing Scheme, an
`example of which is illustrated in FIG. 3, or may be queued
`according to a Suitable derivative thereof. Exemplary net
`work node 300 is shown having a priority queuing imple
`mentation with queues 311-314 ranging from Low to High
`priority respectively. Packets 315, 316, and 317, for
`example, arrive at network layer 210 with different priorities
`as may be determined by the contents of, for example, QoS
`information included with an IP header typically associated
`with each of packets 315, 316, and 317 respectively. High
`priority packet 317, for example, may be placed in high
`priority queue 314 by process 320. Incoming medium pri
`ority packet 315 and low priority packet 316 may be placed
`respectively in medium priority queue 313 and low priority
`queue 311 by process 320 when arriving at network layer
`210. Priority queuing may take place at layer 310 which may
`be equivalent to data link layer 230 or an alternative protocol
`layer such as a PPP layer or the like which interfaces with
`data link layer 230. Outbound packets 318a–318d are sent to
`proceSS 231 for queuing in transmit queue 232 according to
`priority with high priority outbound packet 318a being sent
`first as shown. Outbound packets 318a–318d may then be
`transferred to the physical layer by process 231 which may
`be a typical data link process such as HDLC or the like
`where they can be processed in FIFO transmit queue 232 and
`output to physical link 233.
`While LFI and priority queuing described in conjunction
`with FIG. 2 and FIG. 3 may allow for packets to be
`processed more efficiently, it is important to note that
`efficient processing relies on accurate header information
`most often associated with, for example, an IP header for
`priority queuing and for packets which have been
`fragmented, Sequence information is crucial. At lower layers
`however, Such information may not be as readily available
`and in the case of compressed IP headers, Such information
`is unavailable until the IP packet is decompressed. Frag
`mentation at lower layerS require additional header infor
`mation to track fragments peer to peer. It should be noted
`that in a layered protocol it is possible to have fragmentation
`at multiple layers, however each layer must track fragmen
`tation and certain data types may not tolerate certain anoma
`lies which are m