(12) United States Patent
`Balassanian
`
`USOO6629163B1
`(10) Patent No.:
`US 6,629,163 B1
`(45) Date of Patent:
`Sep. 30, 2003
`
`(54) METHOD AND SYSTEM FOR
`DEMULTIPLEXING A FIRST SEQUENCE OF
`PACKET COMPONENTS TO DENTIFY
`SPECIFIC COMPONENTS WHEREN
`SUBSEQUENT COMPONENTS ARE
`PROCESSED WITHOUT RE-IDENTIFYING
`COMPONENTS
`(75) Inventor: Edward Balassanian, Kirkland, WA
`(US)
`
`University of Arizona at Tucson, ACM Transactions on
`Computer Systems, vol. 16, No. 4, Nov. 1998, pp. 321-366.
`O'Malley, Sean W. and Larry L. Peterson, “A Dynamic
`Network Architecture,” University of Arizona, ACM Trans
`actions on Computer Systems (TOCS), vol. 10, No. 2, May
`1992, pp. 110-143.
`Fiuczynski, Marc E. and Brian N. Bershad, “An Extensible
`Protocol Architecture for Application-Specific Network
`ing,” University of Washington at Seattle, Proceedings of the
`(73) Assignee: Implicit Networks, Inc., Bellevue, WA 1996 Winter USENIX Technical Conference.
`(US)
`Pardyak, Przemyslaw and Brian N. Bershad, “Dynamic
`Binding for an Extensible System,” University of Washing
`-
`Subject to any disclaimer, the term of this
`ton at Seattle, Proceedings of the Second USENIX Sympo
`patent is extended or adjusted under 35
`sium on Operating Systems Design and Implementation
`U.S.C. 154(b) by O dayS.
`(OSDI) 1996.
`Bailey, Mary L. et al., “Path Finder: A Pattern-Based Packet
`Classifier,” University of Arizona at Tucson, Proceedings of
`the First Symposium on Operating Systems Design and
`Implementation, USENIX Association, Nov. 1994.
`Mosberger, David, “Scout: A Path-Based Operating Sys
`tem." A Dissertation Submitted to the Faculty of the Depart
`ment of Computer Science, The University of Arizona, pp.
`87–97, 1997.
`* cited by examiner
`
`c:
`- - -
`(*) Notice:
`
`(21) Appl. No.: 09/474,664
`(22) Filed:
`Dec. 29, 1999
`(51) Int. Cl." ......................... G06F 13/00; H04L 12/56;
`HO4L 12/54
`(52) U.S. Cl. ................................. 71033: 710/1: 710/3;
`710/20, 710/38; 710/51; 710/131; 370/401;
`370/487; 370/498; 370/535; 370/536; 370/542
`(58) Field of Search ............................ 710/1, 3, 33, 38,
`710/131, 132, 20, 51; 370/401, 487, 498,
`535, 536,542
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,425,029 A * 6/1995 Hluchy et al. ............. 370/235
`5,568.478 A 10/1996 van Loo, Jr. et al. ....... 370/392
`5,710,917 A
`1/1998 Musa et al. ................. 707/201
`5,870.479 A 2/1999 Feiken et al. .
`... 713/160
`6,101,189 A
`8/2000 Tsuruoka ..........
`... 370/401
`6,157,622 A 12/2000 Tanaka et al. .......
`... 34.0/7.46
`6,275,507 B1 * 8/2001 Anderson et al. ........... 370/487
`6,359,911 B1 * 3/2002 Movshovich et al. ....... 370/536
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`0408132 A1
`
`1/1991
`
`OTHER PUBLICATIONS
`Bhatti, Nina T., et al., “Coyote: A System for Constructing
`Fine-Grain Configurable Communication Services.” The
`
`Primary Examiner-Jeffrey Gaffin
`Assistant Examiner Tammara Peyton
`(74) Attorney, Agent, or Firm-Perkins Coie LLP
`(57)
`ABSTRACT
`A method and System for demultiplexing packets of a
`message is provided. The demultiplexing System receives
`packets of a message, identifies a Sequence of message
`handlers for processing the message, identifies State infor
`mation associated with the message for each message
`handler, and invokes the message handlers passing the
`message and the associated State information. The System
`identifies the message handlers based on the initial data type
`of the message and a target data type. The identified message
`handlers effect the conversion of the data to the target data
`type through various intermediate data types.
`
`44 Claims, 16 Drawing Sheets
`
`-8.
`RWER
`
`UEJE
`
`-88
`Y
`
`43
`
`15t
`
`
`
`
`
`-12
`"SF
`
`- 83
`-24
`3:... I - IAAF
`
`95
`
`388
`
`MESSE
`SEx
`
`838
`
`-i
`
`ESSE
`Sky
`
`FN
`DEMU: I
`
`LBELAF
`- List
`
`ESSAGE
`SE8.
`
`Juniper Ex. 1001-p. 1
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 1 of 16
`
`US 6,629,163 B1
`
`is
`
`149
`
`151
`
`152
`
`f53.
`
`154
`
`155
`
`101
`
`
`
`2 f0
`
`
`
`103
`
`104
`
`DRIVER
`
`-
`
`MESSAGE
`SEND
`
`105
`
`QUEUE
`
`THREAD
`
`LABELMAP
`GET
`
`NA
`
`106
`
`107
`
`108
`
`MESSAGE
`SEND
`
`MESSAGE
`SEND
`
`MESSAGE
`SEND
`
`109
`
`f 10
`
`ff f
`
`MESSAGE
`
`SES - DEMUX
`
`LABELMAP
`
`- a
`
`114
`
`MESSAGE
`SEND
`
`Fig. 1
`
`Juniper Ex. 1001-p. 2
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 2 of 16
`
`US 6,629,163 B1
`
`
`
`
`
`
`
`
`
`300
`
`MEMORY 303
`
`304
`
`DRIVERS
`
`
`
`FORWARDING
`COMPONENT
`
`DEMUX
`COMPONENT
`
`LABEL MAP
`GET
`COMPONENT
`
`PATH
`DATA
`STRUCTURES
`
`
`
`CONVERSION
`ROUTINES
`
`INSTANCE
`DATA
`
`Juniper Ex. 1001-p. 3
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 3 of 16
`
`US 6,629,163 B1
`
`450
`
`TCP
`
`463
`453
`
`(A) |
`
`A
`
`440
`TCP
`
`A
`
`t SESSION
`- 450
`(A) |
`TCP
`
`PATH (Stacklist)
`
`1
`f
`
`443
`
`464
`43.3
`
`A)
`
`452
`
`431
`
`442
`
`431
`
`4.32
`
`431
`
`420
`
`410
`
`423.424.425
`
`AAA
`
`422
`
`421
`
`413414. 415
`
`ETHERNET AAA
`M
`
`I
`411
`
`473
`
`412
`
`472
`
`471
`
`QUEUE
`
`QUEUE
`
`QUEUE
`
`Fig. 4
`
`/\
`PathEntry
`(REFERENCE)
`
`Juniper Ex. 1001-p. 4
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 4 of 16
`
`US 6,629,163 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Message(Queue
`
`505
`PothEnt
`
`
`
`multiplayList
`
`Message(ueue
`MessageOueue
`StackList
`
`StockList
`OPOthEnt
`
`503
`
`-
`
`PathEntry r
`
`s
`
`Address 504
`
`Map
`
`507
`
`OOTLOOe
`TargetKe
`
`MultiplayList
`
`r308
`
`Member
`
`509
`
`StockListEnt
`PathListEntry
`AddressEnt
`Fl
`
`BindinaList
`CurrentBindinC
`
`BindinqList
`
`506
`
`Binding
`
`510
`
`Pohist
`ActivePaths
`
`Binding
`
`5ff
`
`Fig. 5
`
`Juniper Ex. 1001-p. 5
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet S of 16
`
`US 6,629,163 B1
`
`909
`
`909
`
`
`
`
`
`
`
`Juniper Ex. 1001-p. 6
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 6 of 16
`
`US 6,629,163 B1
`
`MessageSend
`
`(Message, PothEntry)
`
`701
`
`
`
`list
`athEntry --> Multipley
`List
`
`702
`
`Pality -->
`Member
`
`
`
`
`
`
`
`
`
`
`
`position =
`PothEntry --> Member -->
`StackListEntry
`
`
`
`
`
`
`
`
`
`
`
`YES
`
`
`
`NextEntry =
`ListNextold
`(position)
`
`
`
`retVal = nextEntry -->
`Member --> Binding -->
`t
`--> MessageHondler
`(Message, nextEntry)
`
`703
`
`Ponntry -->
`Pot
`
`List Head
`nextEntry
`Dato (pothentry
`Path -> StackList)
`
`Demux
`List
`(Message,
`PathEntry --> Address,
`PathEntry
`
`Fig. 7A
`
`Juniper Ex. 1001-p. 7
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 7 of 16
`
`US 6,629,163 B1
`
`Select next
`Candidate path
`in List
`
`NextEntry
`PahEntry
`
`Number of
`Condidate
`Poth X
`
`PathEntry -->
`MultiplayList
`
`716
`
`I
`MessageSend
`(Message, nextEntry
`
`Fig. 7B
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NextEntry -->
`
`t"Eg
`(Message, NextEntry)
`
`715
`PathEntry -->
`MultiplayList = List
`
`Fig. 7C
`
`Juniper Ex. 1001-p. 8
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 8 of 16
`
`US 6,629,163 B1
`
`Message
`Address
`801 PathEntry
`
`Initialize
`Demux
`
`802
`
`
`
`
`
`808
`
`
`
`continued
`
`cession
`
`Nail Binding
`
`810
`
`Fig. 8
`
`Juniper Ex. 1001-p. 9
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 9 of 16
`
`US 6,629,163 B1
`
`909
`
`patin Address =
`pathEntry --> Path -->
`Address
`
`
`
`
`
`
`
`OddressElem P
`pathAddress -->
`CurrentBinding =
`pothEntry --> Member
`--> AddressEntry
`
`Initialize
`Demux
`
`Map
`PathEntry --> Map
`
`message = Message
`path = null
`address Elem
`
`null
`
`SovedStatus = 0
`Status
`demux Continue
`904
`
`
`
`901
`0
`
`902
`
`903
`
`905
`
`YES
`
`status =
`PathEntry --> Poth -->
`Status
`
`demux
`
`NO
`
`s
`
`906
`
`demux
`Continue
`
`907
`
`pathAddress
`Address
`
`demux
`
`initEnd
`
`
`
`
`
`status = demux Continue -911
`binding List =
`pathAddress -->
`BindingList
`
`912
`
`CurrentBinding =
`&pathAddress -->
`CurrentBinding
`postpone = 0
`
`traverse - List DataNext
`session = Null
`
`913
`
`Fig. 9
`
`Juniper Ex. 1001-p. 10
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 10 of 16
`
`US 6,629,163 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1002
`
`pathAddress =
`AddressCO
`PathEntry P,
`Path -> Address,
`PathEntry-> Member
`-> AddressEntry)
`
`Initend
`
`
`
`1001
`
`
`
`Pothntr
`--> EMer
`--> Binding -->
`Figgs ==
`Simplex
`NO
`
`
`
`YES
`
`1003
`
`pathAddress =
`AddressCreate
`(PathEntry -> Path ->
`Address -> URL)
`
`1004
`
`
`
`
`
`bindind
`List DotdNext
`(PathEntry ->
`Path -> Address -->
`BindingList,
`& elem)
`YES -1006
`pathAddress -->
`CurrentBinding =
`List TaiLinsert
`(pathAddress. -->
`BihdingList, binding)
`
`1007
`
`NO
`
`
`
`
`
`
`
`elem
`PathEntry -->
`Member -->
`AddressEntry
`YES
`Return
`
`Fig. 10
`
`Juniper Ex. 1001-p. 11
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 11 of 16
`
`US 6,629,163 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GetNext Binding
`
`binding = traverse
`(BindingList,
`currentBinding)
`
`1 101
`
`f 102
`
`YES
`
`Return
`(binding)
`
`NO
`f f(0.3
`trailList = Lobel.MapGet
`(map --> Output Label,
`map --> Target Label)
`
`
`
`size of
`trailist
`
`>
`
`f 109
`bindin
`1S RE" may
`-> Target key
`
`binding --> Key =
`map --> Target key
`
`
`
`map --> Target key =
`Null
`
`using )
`List Tail (bindingList
`Doto
`
`impTrail =
`ListeddRemove
`(trailList)
`
`Address Extend
`(pathAddress,
`impTrail)
`
`binding =
`List Toil Data
`(binding List)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`f f 12
`YES
`
`1113
`
`NO
`returnist
`Prepare Multicast Paths
`(trailList, map)
`
`Return
`(multiple)
`
`Return
`(break)
`Fig, 11
`
`Juniper Ex. 1001-p. 12
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 12 of 16
`
`US 6,629,163 B1
`
`edge = binding --> Edge
`Edge protocol = edge
`--> Protocol
`
`- 1201
`
`Fig. 12
`
`Status = edge -->
`DemuxKey (message,
`pathAddress, map)
`
`12O2
`
`
`
`
`
`
`
`
`
`1204
`
`f2O3
`
`
`
`1205
`
`binding --> Flags
`1 = Binding-Remove
`
`remove
`
`postpone
`
`traverse = List DataNext
`postpone++
`
`
`
`NO
`
`traverse
`
`ListData Next
`
`
`
`
`
`other
`
`postpone
`
`1206
`YES
`
`Return
`(next binding)
`
`1207
`
`postpone --
`troverse - ListDataPrev
`
`1212
`
`1209
`
`f2O3
`
`<> saves -
`YES
`st
`
`NO
`
`status = Saved status
`Sovedstatus = 0
`
`12to
`
`status = demux
`continue
`
`
`
`
`
`Return
`
`9
`-> Flags & Binding
`R
`
`
`
`Return
`(next binding)
`
`
`
`
`
`Juniper Ex. 1001-p. 13
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 13 of 16
`
`US 6,629,163 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1301
`
`session = TobleGet
`(protocol -> SessionTable,
`& binding -> key)
`
`
`
`1302
`
`
`
`session =
`CreateSession
`(protocol)
`
`session --> key =
`Lobelreference
`(binding --> key)
`
`Table Put
`(protocol -> sessionTable
`& session -> key session
`
`
`
`protocol -->
`CreateSession
`(session)
`
`
`
`1303
`
`1304
`
`1305
`
`1306
`
`Fig. 13
`
`Juniper Ex. 1001-p. 14
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 14 of 16
`
`US 6,629,163 B1
`
`Noli
`
`1405
`
`
`
`1401
`
`
`
`1402
`
`indinn -
`irr --
`edge --> EdgelD
`1403
`
`List DataSet
`(currentBinding,
`binding)
`
`1404
`
`binding -> flags NN0
`simplex
`
`
`
`YES
`
`Return
`(simplex)
`
`No (g)'s "...
`
`session -->
`Eld
`
`-->
`
`
`
`s
`
`SeSSO
`
`f4O6
`binding --> key =
`Label Reference
`(session --> key)
`1407
`
`session --> BindingTable
`edge --> Edgeld =
`binding
`
`
`
`1408
`
`
`
`
`
`
`
`binding
`-> Edge-> eOWe binding --> Flag 1 -
`CreateBinding
`Binding - Remove
`(binding)
`
`
`
`continue
`
`return
`
`Fig. 14
`
`Juniper Ex. 1001-p. 15
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 15 of 16
`
`US 6,629,163 B1
`
`
`
`150f
`
`?
`binding >
`Flags = simplex &&.
`entry,
`ListheadData
`binding -->
`( Es
`NO
`
`em
`1502
`
`elem = null
`shortEntry = null
`
`
`
`Poth &&.
`status ==
`Extend
`
`firstBinding =
`Listedd Dato
`(pothAddress ->
`Binding List)
`
`
`
`
`
`
`
`
`
`entry =
`List DotaNext
`(binding -> Pathlist,
`& elem)
`-1509
`0
`entry = shortEntry
`
`firstBinding
`- ListNextOdto
`SEE -> Poth ->
`StockList, NUL 2. -> Member
`-> Binding & listNext(entry->
`Path -> StackList, entry > member ->
`SlackListEntry) is shortEntry11(entry
`-> Poth-> StockListSize K
`shortEntry --> Path ->
`StockListSize
`
`
`
`1508
`shortEntry = 1
`entry
`
`
`
`
`
`
`
`
`
`
`
`1510
`15ff
`series path - entry -> Path
`NO
`1512
`1513
`Oth
`e-
`a SE- so NO
`= extend
`
`
`
`Create Poth (path Address,
`i.e. m
`PathEntry -> QOS)
`1515 1516
`PothEntry -->
`elem
`verse "Ein
`entry = PothEntry
`
`ExtendPoth
`(path, map, status)
`
`1514
`
`elem = null
`E. - List Headloto
`(path -> StockList)
`
`Juniper Ex. 1001-p. 16
`Juniper v Implicit
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 16 of 16
`
`US 6,629,163 B1
`
`
`
`
`
`
`
`Process
`
`PathEntry --> Path
`
`1601
`1610
`NO - PathEntry -> Palh = path
`
`entry = ListHeadData
`(path -> StackList)
`
`161 f
`
`YES
`
`1602
`PathEntry -> Path
`= = path
`NO
`
`
`
`oldStock = PathEntry ->
`Path -> stocklist
`
`newStock
`path -> StockList
`
`ListNext
`oldFlm
`(oldStock, Null)
`
`ListNext
`elem
`(NewStock, Null)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OldEntry =
`ListbatoNext (oldstock,
`&oldelem) & S".
`ListDataNext (hewStock, k elem)
`8& E. --> Member -->
`Binding== oldEntry
`Member -->
`Binding
`
`Fig. 16
`
`entry = ListDataPrey
`(newStock, & elem)
`
`
`
`Listeddinsert
`(returnlist, Entry)
`
`1612
`
`Juniper Ex. 1001-p. 17
`Juniper v Implicit
`
`

`

`1
`METHOD AND SYSTEM FOR
`DEMULTIPLEXING A FIRST SEQUENCE OF
`PACKET COMPONENTS TO DENTIFY
`SPECIFIC COMPONENTS WHEREN
`SUBSEQUENT COMPONENTS ARE
`PROCESSED WITHOUT RE-IDENTIFYING
`COMPONENTS
`
`TECHNICAL FIELD
`The present invention relates generally to a computer
`System for data demultiplexing.
`
`BACKGROUND
`Computer Systems, which are becoming increasingly
`pervasive, generate data in a wide variety of formats. The
`Internet is an example of interconnected computer Systems
`that generate data in many different formats. Indeed, when
`data is generated on one computer System and is transmitted
`to another computer System to be displayed, the data may be
`converted in many different intermediate formats before it is
`eventually displayed. For example, the generating computer
`System may initially Store the data in a bitmap format. To
`Send the data to another computer System, the computer
`System may first compress the bitmap data and then encrypt
`the compressed data. The computer System may then convert
`that compressed data into a TCP format and then into an IP
`format. The IP formatted data may be converted into a
`transmission format, Such as an ethernet format. The data in
`the transmission format is then Sent to a receiving computer
`System. The receiving computer System would need to
`perform each of these conversions in reverse order to
`convert the data in the bitmap format. In addition, the
`receiving computer System may need to convert the bitmap
`data into a format that is appropriate for rendering on output
`device.
`In order to proceSS data in Such a wide variety of formats,
`both Sending and receiving computer Systems need to have
`many conversion routines available to Support the various
`formats. These computer Systems typically use predefined
`configuration information to load the correct combination of
`conversion routines for processing data. These computer
`Systems also use a proceSS-Oriented approach when proceSS
`ing data with these conversion routines. When using a
`proceSS-Oriented approach, a computer System may create a
`Separate process for each conversion that needs to take
`place. A computer System in certain situations, however, can
`be expected to receive data and to provide data in many
`different formats that may not be known until the data is
`received. The overhead of Statically providing each possible
`Series of conversion routines is very high. For example, a
`computer System that Serves as a central controller for data
`received within a home would be expected to process data
`received via telephone lines, cable TV lines, and satellite
`connections in many different formats. The central controller
`would be expected to output the data to computer displayS,
`television displays, entertainment centers, Speakers, record
`ing devices, and So on in many different formats. Moreover,
`Since the various conversion routines may be developed by
`different organizations, it may not be easy to identify that the
`output format of one conversion routine is compatible with
`the input format of another conversion routine.
`It would be desirable to have a technique for dynamically
`identifying a Series of conversion routines for processing
`data. In addition, it would be desirable to have a technique
`in which the output format of one conversion routine can be
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,629,163 B1
`
`2
`identified as being compatible with the input format of
`another conversion routine. It would also be desirable to
`Store the identification of a Series of conversion routines So
`that the Series can be quickly identified when data is
`received.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram illustrating example processing
`of a message by the conversion System.
`FIG. 2 is a block diagram illustrating a Sequence of edges.
`FIG. 3 is a block diagram illustrating components of the
`conversion System in one embodiment.
`FIG. 4 is a block diagram illustrating example path data
`Structures in one embodiment.
`FIG. 5 is a block diagram that illustrates the interrela
`tionship of the data structures of a path.
`FIG. 6 is a block diagram that illustrates the interrela
`tionship of the data structures associated with a Session.
`FIGS. 7A, 7B, and 7C comprise a flow diagram illustrat
`ing the processing of the message Send routine.
`FIG. 8 is a flow diagram of the demux routine.
`FIG. 9 is a flow diagram of the initialize demux routine.
`FIG. 10 is a flow diagram of the init end routine.
`FIG. 11 is a flow diagram of a routine to get the next
`binding.
`FIG. 12 is a flow diagram of the get key routine.
`FIG. 13 is a flow diagram of the get session routine.
`FIG. 14 is a flow diagram of the nail binding routine.
`FIG. 15 is a flow diagram of the find path routine.
`FIG. 16 is a flow diagram of the process of path hopping
`routine.
`
`DETAILED DESCRIPTION
`A method and System for converting a message that may
`contain multiple packets from an Source format into a target
`format. When a packet of a message is received, the con
`version System in one embodiment Searches for and identi
`fies a sequence of conversion routines (or more generally
`message handlers) for processing the packets of the message
`by comparing the input and output formats of the conversion
`routines. (A message is a collection of data that is related in
`Some way, Such as Stream of Video or audio data or an email
`message.) The identified Sequence of conversion routines is
`used to convert the message from the Source format to the
`target format using various intermediate formats. The con
`version System then queues the packet for processing by the
`identified Sequence of conversion routines. The conversion
`System Stores the identified Sequence So that the Sequence
`can be quickly found (without searching) when the next
`packet in the message is received. When Subsequent packets
`of the message are received, the conversion System identifies
`the Sequence and queues the packets for pressing by the
`Sequence. Because the conversion System receives multiple
`messages with different Source and target formats and iden
`tifies a Sequence of conversion routines for each message,
`the conversion systems effectively “demultiplexes” the mes
`Sages. That is, the conversion System demultiplexes the
`messages by receiving the message, identifying the
`Sequence of conversion routines, and controlling the pro
`cessing of each message by the identified Sequence.
`Moreover, Since the conversion routines may need to retain
`State information between the receipt of one packet of a
`message and the next packet of that message, the conversion
`
`Juniper Ex. 1001-p. 18
`Juniper v Implicit
`
`

`

`US 6,629,163 B1
`
`15
`
`25
`
`35
`
`40
`
`3
`System maintains State information as an instance or Session
`of the conversion routine. The conversion System routes all
`packets for a message through the same Session of each
`conversion routine So that the same State or instance infor
`mation can be used by all packets of the message. A 5
`Sequence of Sessions of conversion routines is referred to as
`a “path.” In one embodiment, each path has a path thread
`asSociated with it for processing of each packet destined for
`that path.
`In one embodiment, the packets of the messages are
`initially received by “drivers,” such as an Ethernet driver.
`When a driver receives a packet, it forwards the packet to a
`forwarding component of the conversion System. The for
`warding component is responsible for identifying the Session
`of the conversion routine that should next process the packet
`and invoking that conversion routine. When invoked by a
`driver, the forwarding component may use a demultiplexing
`(“demux”) component to identify the session of the first
`conversion routine of the path that is to process the packet
`and then queues the packet for processing by the path. A path
`thread is associated with each path. Each path thread is
`responsible for retrieving packets from the queue of its path
`and forwarding the packets to the forwarding component.
`When the forwarding component is invoked by a path
`thread, it initially invokes the first conversion routine in the
`path. That conversion routine processes the packet and
`forwards the processed packet to the forwarding component,
`which then invokes the Second conversion routine in the
`path. The process of invoking the conversion routines and
`forwarding the processed packet to the next conversion
`routine continues until the last conversion routine in the path
`is invoked. A conversion routine may defer invocation of the
`forwarding component until it aggregates multiple packets
`or may invoke the forwarding component multiple times for
`a packet once for each Sub-packet.
`The forwarding component identifies the next conversion
`routine in the path using the demux component and Stores
`that identification So that the forwarding component can
`quickly identify the conversion routine when Subsequent
`packets of the Same message are received. The demux
`component Searches for the conversion routine and Session
`that is to next process a packet. The demux component then
`Stores the identification of the Session and conversion rou
`tine as part of a path data Structure So that the conversion
`System does not need to Search for the Session and conver
`Sion routine when requested to demultiplex Subsequent
`packets of the same message. When Searching for the next
`conversion routine, the demux component invokes a label
`map get component that identifies the next conversion
`routine. Once the conversion routine is found, the demux
`component identifies the Session associated with that mes
`Sage by, in one embodiment, invoking code associated with
`the conversion routine. In general, the code of the conver
`Sion routine determines what Session should be associated
`with a message. In certain situations, multiple messages may
`share the same Session. The demux component then extends
`the path for processing that packet to include that Session
`and conversion routine. The Sessions are identified So that
`each packet is associated with the appropriate State infor
`mation. The dynamic identification of conversion routines is
`described in U.S. patent application Ser. No. 09/304,973,
`filed on May 4, 1999, entitled “Method and System for
`Generating a Mapping Between Types of Data,” which is
`hereby incorporated by reference.
`FIG. 1 is a block diagram illustrating example processing
`of a message by the conversion system. The driver 101
`receives the packets of the message from a network. The
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`driver performs any appropriate processing of the packet and
`invokes a message Send routine passing the processed packet
`along with a reference path entry 150. The message send
`routine is an embodiment of the forwarding component. A
`path is represented by a Series of path entries, which are
`represented by triangles. Each member path entry represents
`a Session and conversion routine of the path, and a reference
`path entry represents the overall path. The passed reference
`path entry 150 indicates to the message send routine that it
`is being invoked by a driver. The message Send routine
`invokes the demux routine 102 to search for and identify the
`path of Sessions that is to process the packet. The demux
`routine may in turn invoke the label map get routine 104 to
`identify a Sequence of conversion routines for processing the
`packet. In this example, the label map get routine identifies
`the first three conversion routines, and the demux routine
`creates the member path entries 151,152, 153 of the path for
`these conversion routines. Each path entry identifies a Ses
`Sion for a conversion routine, and the Sequence of path
`entries 151-155 identifies a path. The message send routine
`then queues the packet on the queue 149 for the path that is
`to process the packets of the message. The path thread 105
`for the path retrieves the packet from the queue and invokes
`the message Send routine 106 passing the packet and an
`indication of the path. The message Send routine determines
`that the next Session and conversion routine as indicated by
`path entry 151 has already been found. The message send
`routine then invokes the instance of the conversion routine
`for the Session. The conversion routine processes the packet
`and then invokes the message send routine 107. This pro
`cessing continues until the message Send routine invokes the
`demux routine 110 after the packet is processed by the
`conversion routine represented by path entry 153. The
`demux routine examines the path and determines that it has
`no more path entries. The demux routine then invokes the
`label map get routine 111 to identify the conversion routines
`for further processing of the packet. When the conversion
`routines are identified, the demux routine adds path entries
`154, 155 to the path. The messages send routine invokes the
`conversion routine associated with path entry 154.
`Eventually, the conversion routine associated with path
`entry 155 performs the final processing for the path.
`The label map get routine identifies a Sequence of "edges'
`for converting data in one format into another format. Each
`edge corresponds to a conversion routine for converting data
`from one format to another. Each edge is part of a “protocol
`(or more generally a component) that may include multiple
`related edges. For example, a protocol may have edges that
`each convert data in one format into Several different for
`mats. Each edge has an input format and an output format.
`The label map get routine identifies a Sequence of edges Such
`that the output format of each edge is compatible with the
`input format of another edge in the Sequence, except for the
`input format of the first edge in the Sequence and the output
`format of the last edge in the Sequence. FIG. 2 is a block
`diagram illustrating a Sequence of edges. Protocol P1
`includes an edge for converting format D1 to format D2 and
`an edge for converting format D1 to format D3; protocol P2
`includes an edge for converting format D2 to format D5, and
`so on. A sequence for converting format D1 to format D15
`is shown by the curved lines and is defined by the address
`“P1:1, P2:1, P3:2, P4:7.” When a packet of data in format
`D1 is processed by this Sequence, it is converted to format
`D15. During the process, the packet of data is Sequentially
`converted to format D2, D5, and D13. The output format of
`protocol P2, edge 1 (i.e., P2:1) is format D5, but the input
`format of P3:2 is format D10. The label map get routine uses
`
`Juniper Ex. 1001-p. 19
`Juniper v Implicit
`
`

`

`US 6,629,163 B1
`
`15
`
`25
`
`35
`
`40
`
`S
`an aliasing mechanism by which two formats, Such as D5
`and D10 are identified as being compatible. The use of
`aliasing allows different names of the same format or
`compatible formats to be correlated.
`FIG. 3 is a block diagram illustrating components of the
`conversion System in one embodiment. The conversion
`System 300 can operate on a computer System with a central
`processing unit 301, I/O devices 302, and memory 303. The
`I/O devices may include an Internet connection, a connec
`tion to various output devices Such as a television, and a
`connection to various input devices Such as a television
`receiver. The media mapping System may be Stored as
`instructions on a computer-readable medium, Such as a disk
`drive, memory, or data transmission medium. The data
`Structures of the media mapping System may also be Stored
`on a computer-readable medium. The conversion System
`includes drivers 304, a forwarding component 305, a demux
`component 306, a label map get component 307, path data
`structures 308, conversion routines 309, and instance data
`310. Each driver receives data in a source format and
`forwards the data to the forwarding component. The for
`warding component identifies the next conversion routine in
`the path and invokes that conversion routine to process a
`packet. The forwarding component may invoke the demux
`component to Search for the next conversion routine and add
`that conversion routine to the path. The demux component
`may invoke the label map get component to identify the next
`conversion routine to process the packet. The demux com
`ponent Stores information defining the paths in the path
`Structures. The conversion routines Store their State infor
`mation in the instance data.
`FIG. 4 is a block diagram illustrating example path data
`Structures in one embodiment. The demux component iden
`tifies a Sequence of "edges' for converting data in one
`format into another format by invoking the label map get
`component. Each edge corresponds to a conversion routine
`for converting data from one format to another. AS discussed
`above, each edge is part of a “protocol’ that may include
`multiple related edges. For example, a protocol may have
`edges that each convert data in one format into Several
`different formats. Each edge has as an input format ("input
`label') and an output format (“output label”). Each rectangle
`represents a session 410, 420, 430, 440, 450 for a protocol.
`A Session corresponds to an instance of a protocol. That is,
`the Session includes the protocol and State information
`associated with that instance of the protocol. Session 410
`corresponds to a Session for an Ethernet protocol; Session
`420 corresponds to a Session for an IP protocol; and Sessions
`430, 440, 450 correspond to sessions for a TCP protocol.
`FIG. 4 illustrates three paths 461, 462, 463. Each path
`includes edges 411, 421, 431. The paths share the same
`Ethernet session 410 and IP session 420, but each path has
`a unique TCP session 430, 440, 450. Thus, path 461 includes
`sessions 410, 420, and 430; path 462 includes sessions 410,
`420, and 440; and path 463 includes sessions 410, 420, and
`450. The conversion system represents each path by a
`Sequence of path entry Structures. Each path entry Structure
`is represented by a triangle. Thus, path 461 is represented by
`path entries 415, 425, and 433. The conversion system
`represents the path entries of a path by a Stack list. Each path
`also has a queue 471, 472, 473 associated with it. Each
`queue Stores the messages that are to be processed by the
`conversion routines of the edges of the path. Each Session
`includes a binding 412, 422, 432, 442, 452 that is repre
`Sented by an oblong shape adjacent to the corresponding
`edge. A binding for an edge of a Session represents those
`paths that include the edge. The binding 412 indicates that
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`three paths are bound (or “nailed”) to edge 411 of the
`Ethernet session 410. The conversion system uses a path list
`to track the paths that are bound to a binding. The path list
`of binding 412 identifies path entries 413, 414, and 415.
`FIG. 5 is a block diagram that illustrates the interrela
`tionship of the data Structures of a path. Each path has a
`corresponding path Structure 501 that contains Status infor
`mation and pointers to a message queue Structure 502, a
`stack list structure 503, and a path address structure 504. The
`Status of a path can be extend, continue, or end. Each
`message handler returns a status for the path. The Status of
`extend means that additional path entries should be added to
`the path. The status of end means that this path should end
`at this point and Subsequent processing should continue at a
`new path. The Status of continue means that the protocol
`does not care how the path is handled. In