`
`
`
`
`Exhibit H
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 2 of 23
`I 1111111111111111 11111 111111111111111 lllll 111111111111111 lll111111111111111
`US008116315B2
`
`c12) United States Patent
`Posey, Jr.
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 8,116,315 B2
`*Feb.14,2012
`
`(54) SYSTEM AND METHOD FOR PACKET
`CLASSIFICATION
`
`(75)
`
`Inventor: Nolan J. Posey, Jr., Allen, TX (US)
`
`(73) Assignee: YT Networks Capital, LLC,
`Wilmington, DE (US)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,253,248 A
`10/ 1993 Dravida et al.
`(Continued)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 615 days.
`
`EP
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`(21) Appl. No.: 11/471,149
`
`(22) Filed:
`
`Jun.20,2006
`
`(65)
`
`Prior Publication Data
`
`US 2006/0239288 Al
`
`Oct. 26, 2006
`
`(63)
`
`(51)
`
`(52)
`
`(58)
`
`Related U.S. Application Data
`
`Continuation of application No. 10/138,760, filed on
`May 3, 2002, now Pat. No. 7,184,444, which is a
`continuation-in-part of application No. 09/698,666,
`filed on Oct. 27, 2000, now Pat. No. 6,665,495.
`
`Int. Cl.
`(2006.01)
`H04L 12128
`(2006.01)
`H04L 12156
`(2006.01)
`H04L 1100
`(2006.01)
`H04L 12126
`(2006.01)
`H04L 12154
`(2006.01)
`G06F 151173
`(2006.01)
`G06F 15116
`U.S. Cl. .............. 370/395.31; 370/395.43; 370/392;
`370/395.1; 370/252; 370/398; 370/422; 370/428;
`709/224; 709/249
`Field of Classification Search ............. 370/395.31,
`370/395.43, 392,395, 252, 389, 393, 395.1,
`370/398, 395.6, 422, 428; 709/224, 249
`See application file for complete search history.
`
`FOREIGN PATENT DOCUMENTS
`0849916 A2
`6/1998
`(Continued)
`
`OTHER PUBLICATIONS
`
`Borgonovo et al. Unslotted deflection routing in all-optical networks;
`Global Teleconununications Conference, 1993, including a Conunu(cid:173)
`nication Theory Mini-Conference. Technical Program Conference
`Record, IEEE in Houston. GLOBECOM '93., IEEE, Nov. 29-Dec. 2,
`1993.
`
`(Continued)
`
`Primary Examiner - Ronald Abelson
`(74) Attorney, Agent, or Firm -Connolly Bove Lodge &
`Hutz LLP
`
`(57)
`
`ABSTRACT
`
`The present invention provides method for data packet pro(cid:173)
`cessing in a telecommunications system. The method of the
`present invention can include the steps of (i) determining a set
`of classification parameters for a data packet at an ingress
`edge unit, wherein the classification parameters include a
`packet destination, (ii) communicating the data packet to an
`egress edge unit and (iii) routing the data packet to a destina(cid:173)
`tion egress port at the egress edge unit according the classi(cid:173)
`fication parameters determined at the ingress edge unit. In one
`embodiment of the present invention, the classification
`parameters can include a destination egress edge unit, a des(cid:173)
`tination egress port at the destination egress edge unit, and
`quality of service parameter for proper processing of the data
`packet.
`
`21 Claims, 8 Drawing Sheets
`
`110
`
`'"
`
`~35
`
`X
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 3 of 23
`
`US 8,116,315 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`5,303,078 A
`4/1994 Brackett et al.
`5,327,552 A
`7/1994 Liew
`5,351,146 A
`9/1994 Chan et al.
`5,416,769 A
`5/1995 Karol
`5,469,284 A
`11/1995 Haas
`5,477,530 A
`12/1995 Ahmadi et al.
`5,486,943 A
`1/1996 Sasayama et al.
`5,546,391 A *
`8/1996 Hochschild et al.
`5,617,413 A
`4/1997 Monacos
`5,734,486 A
`3/1998 Guillemot et al.
`5,737,106 A
`4/1998 Sansonetti et al.
`5,757,526 A
`5/1998 Shiragaki et al.
`5,848,055 A
`12/1998 Fedyk et al.
`5,978,359 A
`11/1999 Caldara et al.
`6,005,698 A
`12/1999 Huber et al.
`6,023,456 A
`2/2000 Chapman
`6,052,726 A
`4/2000 Fontenot
`6,320,858 Bl * 11/2001 King eta!.
`6,345,040 Bl
`2/2002 Stephens et al.
`6,501,869 Bl
`12/2002 Athale
`6,567,408 Bl
`5/2003 Lee
`6,674,754 Bl
`1/2004 Ofek
`6,721,315 Bl
`4/2004 Xiong et al.
`6,763,192 Bl
`7/2004 Jagannathan
`6,782,201 B2
`8/2004 Yamamoto et al.
`6,819,870 Bl
`11/2004 Ge et al.
`6,834,310 B2
`12/2004 Munger et al.
`6,859,579 B2
`2/2005 Shiozawa et al.
`6,907,001 Bl*
`6/2005 Nakayama et al.
`6,928,244 Bl
`8/2005 Goldstein et al.
`6,975,638 Bl * 12/2005 Chen et al.
`7,068,871 B2
`6/2006 Sugamaet al.
`2001/0043562 Al * 11/2001 Hrastar et al.
`2002/0015551 Al
`2/2002 Tsuyama et al.
`2002/0048066 Al
`4/2002 Antoniades et al.
`2002/0080446 Al
`6/2002 Derventzis et al.
`2002/0101869 Al
`8/2002 Garcia-Luna-Aceves
`2003/0030866 Al
`2/2003 Yoo
`2003/0063348 Al
`4/2003 Posey
`2003/0067653 Al
`4/2003 Aicklen
`2004/0151171 Al
`8/2004 Lee et al.
`2009/0067434 Al *
`3/2009 Brueckheimer et al.
`
`WO
`WO
`
`FOREIGN PATENT DOCUMENTS
`WO 95/30318 A2
`11/1995
`WO 00/42811 Al
`7/2000
`
`OTHER PUBLICATIONS
`
`370/413
`
`370/390
`
`370/230
`
`370/412
`
`370/227
`
`370/395.1
`
`Chevalier et al. "A new packet routing strategy for ultra-fast photonic
`networks", Dept. of Electron & Electr. Eng., Strathclyde Univ.,
`Glasgow; This paper appears in: Global Telecommunications Con-
`
`ference, 1998, GLOBECOM '93., "The Bridge to Global Integratio",
`1998.
`Bannister et al., "A performance model of deflection routing in
`multibuffer networks with non-uniform traffic Networking," IEEE/
`ACM Transactions on vol. 3, issue 5, pp. 509-520, Oct. 1995.
`Hunter, David K., "Buffering in optical packet switches", Jrnl. Of
`Lightwave Technology, vol. 16:12, pp. 2081-2094, Dec. 1998.
`Borgonovo et al. "On the design of optical deflection-routing net(cid:173)
`works", INFOCOM '94. Networking for Global Communications.
`13th Proceedings IEEE, Publication Date: Jun. 12-16, 1994, pp. 120-
`129, vol. 1, Meeting Date: Jun. 12, 1194-Jun. 16, 1994.
`Li et al., "Deflection Routing in Slotted Self-Routing Networks with
`Arbitrary Topology," IEEE Jrnl. On Selected Areas in Communica(cid:173)
`tions, vol. 22:9, pp. 1812-1822, Nov. 2004.
`International Search Report for PCT/US0l/51237, Mar. 20, 2003.
`Kanna, et al., "A High Bandwidth Space-Time-Wavelength Multi(cid:173)
`plexed Optical Switching Networlc', Proceedings of the IEEE
`INFOCOM '97, Los Alamitos, CA, Apr. 7-12, 1997.
`McKeown, et al., "Tiny Tera: A Packet Switch Core", IEEE Micro,
`IEEE Inc., New York, vol. 17, No. 1, pp. 26-33, Jan. 1997.
`Soeren Lykke Danielsen, et al., "WDM Packet Switch Architectures
`and Analysis of the Influence ofTuneable Wavelength Converters on
`the Performance", Jun. 1998.
`Soeren L. Danielsen, et al., IEEE Photonics Technology Letters, vol.
`10, No. 6, "Optical Packet Switched Network Layer Without Optical
`Buffers", unknown.
`John M. Senior, et al., SPIE-The International Society of Optical
`Engineering, All-Optical Networking: Architecture, Control and
`Management Issues vol. 3531, pp. 455-464, Nov. 3-5, 1998.
`M.C. Chia, et al., Part of SPIE Conference on All-Optical Network(cid:173)
`ing: Architecture, Control and Management Issues, "Performance of
`Feedback and Feedforward Arrayed-Waveguide Gratings-Based
`Optical Packet Switches with WDM Inputs/Outputs", Nov. 1998.
`G. Depovere, et. al., Philips Research Laboratories, "A Flexible
`Cross-Connect Network Using Multiple Object Carriers" all pages,
`unknown.
`John M. Senior, et al., SPIE-The International Society for Optical
`Engineering, "All-Optical Networking 1999: Architecture, Control,
`and Management Issues" vol. 3843, pp. 111-119, Sep. 19-21, 1999.
`Jonathan S. Turner, Journal of High Speed Networks 8 (1999) 3-16
`IOS Press, "Terabit Burst Switching", pp. 3-16, 1999.
`Ken-ichi Sato, IEEE Journal on Selected Areas in Communications,
`vol. 12, No. 1, Jan. 1994 "Network Performance and Integrity
`Enhancement with Optical Path Layer Technologies", pp. 159-170,
`Jan. 1994.
`F. Callegati, et al., Optical Fiber Technology 4, 1996 "Architecture
`and Performance of a Broadcast and Select Photonic Switch", pp.
`266-284, 1998.
`
`* cited by examiner
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 4 of 23
`
`110
`
`130
`~
`
`131
`)
`
`1t0
`
`,000
`
`127
`
`129
`
`0/ I
`
`e1
`
`l
`
`125
`
`132
`
`I
`
`I
`I
`
`I
`
`/
`
`140
`
`~ I
`
`I
`
`' - ~
`
`'
`
`'
`
`.,ULJJ
`J
`
`~
`00
`•
`~
`~
`~
`
`~ =
`
`~
`
`"f'j
`('D
`?'
`....
`"' ...
`0 ....
`
`N
`
`N
`
`('D
`('D
`
`rJJ =-
`....
`....
`0 ....
`
`QO
`
`115
`
`r---,
`
`117
`~
`
`135
`
`~
`
`I X
`11 ~,r
`
`~21
`
`119
`
`\
`\
`\
`\
`\
`
`12
`
`I
`
`'.JI
`.......
`
`I
`
`I
`
`I
`
`I
`
`I
`
`116
`
`I
`
`I
`
`I
`
`l
`
`r-i r--,
`
`J-
`
`.......
`
`--... --... --...
`
`I= 1 ~
`
`FIGURE 1
`
`d r.,;_
`
`_,,OIO
`"'""'
`"'""' 0--, w
`"'""' UI = N
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 5 of 23
`
`U.S. Patent
`
`Feb. 14,2012
`
`Sheet 2 of 8
`
`US 8,116,315 B2
`
`0
`N
`N
`
`0
`00
`N
`
`'(cid:173)
`
`'-
`
`(cid:143)
`
`(cid:143) IO ,..
`
`w
`
`~ ( ~---+--~-· ~_----_----_, ....... f:-..---7"':;_------....._-----,-..-------,
`
`'
`
`I
`
`0 ,..
`N
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 6 of 23
`
`U.S. Patent
`
`Feb.14,2012
`
`Sheet 3 of 8
`
`US 8,116,315 B2
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 7 of 23
`
`L,
`~
`
`---...---·
`
`-·--------\ o\
`
`L----·----·,---.,· . ,. ··---·
`
`[J
`
`o,
`L_ .... --,. ....... _,.,,_,_,-i
`
`i~~
`
`ri,,'1?
`
`t"1,,'t
`·~------------------------·-----.
`
`Destination: Egress Edge 0
`o,so H H Ill \Hl--------t• I QoS Controller
`o,s,B!IIIIIM-
`
`420
`
`S.ueor P1c\l.ot
`
`- I I l
`
`S1;per Pack.al
`
`l }
`
`Destination: Egress Edge 1
`o,so Ill Ill Ill Ill Ill Ill lil,__:_ ______ ,r 1--::a::::o:::s:--;c::::o::n:::tr:o;;:lle::r-,
`o,s, llllllllll!il~---
`00 111111------------
`:
`a,s K 11!11 m!
`
`I
`
`I
`
`• • •
`
`Destination: Egress Edge (M • 1)
`o,soUllllllUIII
`~
`
`o,s, 11111111111~---_--:::::::::
`' Ill 111111111 -------------(cid:173)
`aoSL B Ill
`
`SuparP1ck:1l
`
`l l r
`
`Super Pa¢ka~
`
`\ I
`
`QoS Controller
`
`39;
`
`SuperP1ck.1t
`
`\\
`
`1
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`"f'j
`
`~ ....
`0 ....
`
`.i;...
`"'
`N
`
`N
`
`rJJ =(cid:173)
`('D a
`0 ....
`
`.i;...
`
`QO
`
`Flt vt2 -E. Lj
`
`d r.,;_
`00
`"'
`"'""'
`"'""' 0--, w
`"'""' UI = N
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 8 of 23
`
`Figure 5A
`
`/500
`
`510
`
`Common Overhead
`
`Port Bundle Entries
`
`530
`
`540
`
`{
`
`{
`
`550
`
`Source Edge:
`0111
`Des tin at ion Edae
`1111
`42
`Seauence Number,
`000
`Status Bits:
`0
`1
`Number of Port Bundles:
`10
`Offset to Port Bundle:
`Status Bits:
`0 1 1 0
`Index Tvoe:
`0001
`Version:
`0000
`8
`Number of PPEs:
`Per Packet Entries 00: 0
`32
`1000
`1111
`01: 0, 65,536
`1111 1000
`64
`02: 0
`0011
`0000
`03: 0
`535
`0111
`0011
`04: 0
`1 492
`0001
`0000
`05: 0
`1 492
`0000
`0000
`06: 0
`1 492
`0000
`0110
`07: 0
`5 273
`1111 1000
`Packet 00
`Packet 01
`Packet 02
`Packet 03
`Packet 04
`Packet 05
`
`Packets
`
`520
`
`...
`
`:Packet N-1
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`"f'j
`('D
`
`?' ....
`"' ...
`0 ....
`
`N
`
`N
`
`('D
`
`rJJ =-('D
`.....
`Ul
`0 ....
`
`QO
`
`d r.,;_
`
`_,,OIO
`"""'
`"""' 0--, w
`"""' UI = N
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 9 of 23
`
`Figure 5B
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`"f'j
`('D
`
`?' ....
`0 ....
`
`,i;...
`"'
`N
`
`N
`
`520
`
`Packet Buffer
`
`Packet 00
`Packet 01
`Packet 02
`Packet 03
`Packet 04
`Packet 05
`Packet 06
`Packet 07
`Packet 08
`Packet 09
`Packet 10
`Packet 11
`Packet 12
`Packet 13
`Packet 14
`Packet 15
`Packet 16
`
`~ ... ... ... ... ...
`~ ... ... ... ... ...
`
`~
`f.-
`
`Port
`Bundle Overhead
`
`Status Bits
`Index Type
`Version
`Nurrber of PPEs
`
`}540
`
`Per Packet Entry
`~ .. ...
`~ ,..
`~ ....
`... ....
`... ...
`~ ..
`~ ..
`
`00: M, Lenoth, Port, Queue
`01: M Lenoth Port Queue
`02: M Lenath Port Queue
`03: M Lenath Port Queue
`04: M Lenath Port Queue
`05: M Lenoth Port Queue
`06: M Lenoth Port Queue
`07: M, Length, Port, Queue
`
`550
`
`rJJ =-('D
`('D ....
`0 ....
`
`O'I
`
`QO
`
`d r.,;_
`
`_,,OIO
`""'"'
`""'"' 0--, w
`""'"' UI = N
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 10 of 23
`
`Figure 5C
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`I
`
`,
`
`~
`
`,
`
`~
`
`Common Overhead
`
`Source 6:Jqe
`Destination 6:Jqe
`Sequence Nurrber
`Status Bits
`Index Type
`Version
`Nurrber of Port Bundles
`
`Port
`Bundle Entries
`Offs et to Port Bundle 00
`Status Bits
`Index Tvoe
`Version
`Nurrber of PPEs
`Offset to Port Bundle 01
`Status Bits
`Index Type
`Version
`Nu rrber of PPEs
`
`Offset to Port Bundie B-1
`Status Bits
`_ --
`Index~
`Version
`Nurrber of PPEs
`
`530
`
`I
`
`540
`
`540
`
`540
`
`{
`
`575
`
`.. "'1
`I . ...
`
`I
`.. ....
`I
`
`Port Bundles
`
`PPEs Port Bundle 00
`Packet Bundle Port 00
`
`PPEs Port Bundle 01
`Packet Bundle Port 01
`
`. .
`
`PPEs Port Bundle B-1
`P'acket Bundle Port P-1
`
`I
`
`--- 550
`-520
`_,-550
`I
`l
`-520
`
`_,-550
`l
`I
`-s20
`
`"f'j
`('D
`
`?' ....
`"' ...
`0 ....
`
`N
`
`N
`
`('D
`
`rJJ =-('D
`.....
`-....J
`0 ....
`
`QO
`
`d r.,;_
`
`_,,OIO
`"""'
`"""' 0--, w
`"""' UI = N
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 11 of 23
`
`Figure 5D
`
`t~
`
`[oclV
`
`Super Packet
`
`1
`
`Egress Frag Buffers
`1 for each Edge
`
`Current L~ _ii _i _m _ii _I _i _i_~ _[ _:_:_:_:: _::::
`Tail
`Frag
`
`~
`
`Previous Head Fra
`·~~ 00
`
`4,10
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`"f'j
`('D
`
`?' ....
`"' ...
`0 ....
`
`N
`
`N
`
`('D
`('D
`
`rJJ =(cid:173)
`.....
`QO
`0 ....
`
`QO
`
`d r.,;_
`
`_,,OIO
`"'""'
`"'""' 0--, w
`"'""' UI = N
`
`01
`02
`03
`04
`05
`06
`07
`08
`09
`10
`II
`12
`13
`14
`15
`
`Ingress
`Frag Buffer
`1 for each SPF
`
`Next
`Ta i l~
`Frag
`\.,.
`1oc;D
`
`,
`
`.,
`
`---_ .. -_ ..
`2 -
`
`Current He*d Frag
`
`b7D
`
`I
`
`I
`
`i
`(;.10
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 12 of 23
`
`US 8,116,315 B2
`
`1
`SYSTEM AND METHOD FOR PACKET
`CLASSIFICATION
`
`RELATED APPLICATIONS
`
`2
`classification system and a method that can perform the clas(cid:173)
`sification only at the ingress edge unit, thus reducing the
`complexity and computational requirements at the egress
`edge unit.
`
`SUMMARY OF THE INVENTION
`
`The present invention provides a data packet classification
`system and method that substantially eliminates or reduces
`disadvantages and problems associated with previously
`developed data packet classification systems and methods
`used in telecommunications networks.
`More specifically the present invention provides method
`for data packet classification in a telecommunications sys(cid:173)
`tem. The method of the present invention can include the
`steps of (i) determining a set of classification parameters for
`a data packet at an ingress edge unit, wherein the classifica(cid:173)
`tion parameters include a packet destination, (ii) communi-
`20 eating the data packet to an egress edge unit and (iii) routing
`the data packet to a destination egress port at the egress edge
`unit according the classification parameters determined at the
`ingress edge unit. In one embodiment of the present inven(cid:173)
`tion, the classification parameters can include a destination
`25 egress edge unit, a destination egress port at the destination
`egress edge unit, and quality of service parameter for proper
`processing of the data packet.
`The present invention provides substantial technical
`advantage over previously developed systems and methods
`30 for routing data packets because the present invention can
`route data packets to an egress port without reclassifying the
`data packet at the egress edge unit associated with the port,
`thus minimizing duplicative hardware and processing
`requirements at the egress edge unit.
`The present invention provides another substantial advan-
`tage over previous systems and methods for routing data
`packets by eliminating the delay caused by reclassifying a
`data packet at an egress edge unit, thereby increasing the
`throughput of optical routers/switches utilizing the present
`40 invention.
`The present invention provides yet another technical
`advantage by allowing the routing of multiple data packets to
`a single destination edge unit.
`
`This application is a continuation of and claims priority
`under 35 U.S.C. 120 from U.S. patent application Ser. No.
`10,138,760, filed May 3, 2002, entitled "SYSTEM AND
`METHOD FOR PACKET CLASSIFICATION," now U.S.
`Pat. No. 7,184,444, which is a continuation-in-part of U.S. 10
`patent application Ser. No. 09/698,666, filed Oct. 27, 2000,
`entitled "Non-Blocking, Scalable Optical Router Architec(cid:173)
`ture and Method for Routing Optical Traffic," now U.S. Pat.
`No. 6,665,495, both of which are hereby fully incorporated
`by reference.
`
`15
`
`TECHNICAL FIELD OF THE INVENTION
`
`The present invention relates generally to telecommunica(cid:173)
`tion systems and methods, and more particularly, a system
`and method for classification of data packets to facilitate the
`routing of the data packets.
`
`BACKGROUND OF THE INVENTION
`
`In telecommunications networks, routers and switches are
`used to direct data packets from a data packet's origin to its
`destination. Often a router or switch will have multiple
`incoming and outgoing transmission lines ( or "ports").
`Therefore, to route a packet through a telecommunications
`network, it is necessary to properly internally route the data
`packet at each router or switch from the incoming transmis(cid:173)
`sion port to the proper outgoing transmission port. This is
`commonly achieved by classifying the packets at the ingress
`edge of the switch/router. This classification of data packets 35
`can include determining the egress edge unit of the switch/
`router to which a particular data package should be routed. In
`this manner, data packets can be switched from a particular
`incoming transmission port to a particular outgoing transmis(cid:173)
`sion port through the switch/router.
`In current data packet classification and routing systems, a
`data packet arrives at an ingress interface unit of a router
`where packet classification occurs. During packet classifica(cid:173)
`tion, current systems will classify the data packet based on its
`destination port, which is associated with a particular egress 45
`edge unit. According to the classification, the router will route
`the data packet to the appropriate egress edge unit of the
`optical network for further routing. In current optical net(cid:173)
`works, however, the classification of a data packet is typically
`not retained once the data packet leaves the ingress edge unit 50
`in route to the egress edge unit.
`In operation, data packets are classified in current systems
`and methods for classifying data packets based on the desti(cid:173)
`nation egress edge unit. When a packet arrives at the destina(cid:173)
`tion egress edge unit, classification is repeated to determine 55
`the destination egress interface port of the egress edge unit.
`Thus, the processing to determine the destination occurs in
`two stages. First it occurs at the ingress edge unit to determine
`to which egress edge unit a data package is bound and, again,
`at the egress edge unit to determine to which egress interface 60
`port the data package should be routed. Because classification
`occurs both at the ingress edge unit and the egress edge unit,
`current optical networks require that there be classification
`hardware at both units.
`As noted, prior art packet classification systems and meth- 65
`ods require repeating the classification process at the egress
`edge interface unit. Therefore, a need exists for a packet
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A more complete understanding of the present invention
`and the advantages thereof may be acquired by referring to
`the following description, taken in conjunction with the
`accompanying drawings in which like reference numbers
`indicate like features and wherein:
`FIG. 1 is a diagrammatic representation of one embodi(cid:173)
`ment of a router 100 that can perform data packet classifica(cid:173)
`tion at the ingress edge unit according to the present inven(cid:173)
`tion;
`FIG. 2 is a diagrammatic representation of a second
`embodiment of a router that can perform data packet classi(cid:173)
`fication according to the present invention;
`15 FIG. 3 is a diagrammatic representation of one embodi(cid:173)
`ment of an ingress edge unit that can perform packet classi(cid:173)
`fication according to the present invention;
`FIG. 4 is a diagrammatic representation of a second
`embodiment of an ingress edge unit that can perform packet
`classification according to the present invention;
`FIG. SA illustrates one embodiment of super packet con(cid:173)
`taining a classification index according to the present inven(cid:173)
`tion;
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 13 of 23
`
`US 8,116,315 B2
`
`3
`FIG. SB illustrates one embodiment of a port bundle con(cid:173)
`struction containing a classification index according to the
`present invention;
`FIG. SC illustrates one embodiment of a super packet con(cid:173)
`struction containing a classification index according to the
`present invention; and
`FIG. SD illustrates one embodiment of combining frag(cid:173)
`ments of packets from arriving super packets.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`Preferred embodiments of the present invention are illus(cid:173)
`trated in the figures like numerals being used to refer to like
`and corresponding parts of the various drawings.
`The invention provides a data packet classification system
`and method wherein a data packet can be classified at the
`ingress edge unit of a router/switch. The data packet can be
`routed to its destination egress interface port based on the
`classification parameters that were determined at the ingress
`edge unit of the router/switch. Because classification does not
`have to be repeated at the egress edge unit, duplicative pro(cid:173)
`cessing and hardware requirements are substantially reduced.
`FIG. 1 is a diagrammatic representation of one embodi(cid:173)
`ment of a router 100 that can perform data packet classifica(cid:173)
`tion at the ingress edge unit according to the present inven(cid:173)
`tion. Router 100 can include a number of ingress edge units
`110 (shown in FIG. I as sixteen ingress edge units labeled
`Il,I2,I3 ... 116), a number of egress edge units: (shown in
`FIG.1 as sixteen egress edge units labeled El, E2, E3 ... E16)
`and an optical switch core 130 that comprises a switch fabric
`135 and a controller 140. While each of the edge units is
`illustrated separately for the sake of simplicity, it should be
`understood that edge units comprising both an ingress edge
`unit and an egress edge unit in the same physical structure can
`be constructed. Each of the edge units 110 can communicate
`data to switch fabric 135 via ingress packet links 117 and each
`egress edge unit can receive data from switch fabric 135 via
`egress packet links 127. In one embodiment of the present
`invention the ingress packet links 117 and egress packet links
`127 can beDWDMlinks.Additionally, each ingress edge unit
`and each egress edge unit can receive and communicate con(cid:173)
`trol information with controller 140 via ingress control links
`119 and egress control links 129, respectively.
`Each ingress edge unit 110 and each egress edge unit 120 of
`router 100 can include a variety of ingress interface ports 115 45
`and egress interface ports 125, respectively, which can exter(cid:173)
`nally connect to an assortment of other network elements
`such as switches, routers, cross-connects and/or transmission
`equipment. The ingress interface ports 115 and egress inter(cid:173)
`face ports 125 can support, for example, high bandwidth IP 50
`traffic and/or TDM traffic. In one embodiment of the present
`invention, each of these ports can support 10 Gbps and above.
`In operation, data packets can arrive at an ingress edge unit
`110 through the ingress interface ports 115. At each ingress
`interface port 115, an ingress port card 116 associated with an 55
`ingress interface port 115 can determine a set of classification
`parameters for an incoming data packet. In one embodiment,
`the classification parameters can include a destination egress
`edge unit and a destination egress interface port. Additionally,
`the classification parameters might include a quality of ser- 60
`vice ("QoS") parameter, including the type of service bits,
`source IP address, layer four and five classification, service
`level agreements, operator configuration and the QoS soft(cid:173)
`ware in use. The classification parameters can be forwarded
`from each ingress port card 116 to controller 140 via ingress 65
`control links 119. Additionally, the classification parameters
`can be placed in a classification index for the data packet. The
`
`4
`classification index can be included in the overhead of the
`data packet sent to the egress edge unit.
`Controller 140 can collect data from each ingress edge unit
`110, egress edge unit 120 and switch fabric 135 on a periodic
`5 basis ( e.g., every millisecond), create a schedule that effects
`each ingress edge unit 110 and egress edge unit 120 for the
`next cycle, and provide the schedule to each ingress edge unit
`110 and each egress edge unit 120. During scheduling, con(cid:173)
`troller 140 can use quality of service parameters to determine
`10 which of the arriving data packets should be sent at any given
`time or whether a data packet should be dropped ( e.g., in a
`congestion situation). Algorithms such as random early
`detection, weighted random early detection, early packet dis(cid:173)
`card and other algorithms could be used to determine which
`15 packets should be dropped. Based on this schedule, ingress
`port card 116 can place an incoming data packet in a QoS
`queue (for subsequent forwarding to TWDM converter 118)
`or forward the data directly to TWDM converter 118. Ingress
`port card 116 can maintain multiple QoS queues for each
`20 egress interface port 125.
`At TWDM converter 118 data packets from each ingress
`interface port card 116 can be forwarded to wave slot (µA)
`buffers. There can be multiple µA buffers for each ingress
`interface port 115, and the number of µA buffers for each
`25 ingress interface port 115 can correspond to the number of
`egress interface ports 125 ( e.g., if there are K egress interface
`ports there can be K µA buffers for each ingress interface
`port). Data packets arriving at each ingress interface port 115
`can be directed to the µA buffer associated with the destination
`30 egress interface port 125 to which the data packet is bound.
`Thus, in one embodiment of the present invention, each µA
`can contain data packets from the same ingress interface port
`115 that are bound to the same egress interface port 125.
`When the loading of the µA buffers is complete for a cycle,
`35 the TWDM converter 118 can subdivide the available µAs into
`as many channels as there are wavelengths utilized by the
`ingress packet links 117. It should be noted that each µA can
`include zero data packets, a single data packet, or multiple
`data packets bound for the same egress interface port 125.
`40 DWDM transmitter 121 can then forward a µA to optical
`switch fabric 135 for further routing to the destination egress
`edge unit. Each µA can be forwarded across multiple data
`streams, one stream per lambda as supported by the DWDM
`lambda count.
`As µAs pass through optical switch fabric 135, controller
`140 can control the configuration of switch fabric 135 so that
`each µA is routed to the appropriate egress edge unit 120.
`Because controller 140 can dynamically reconfigure switch
`fabric 135 based on the schedule that it established, conflicts
`and contentions of µAs in switch fabric 135 can be avoided. At
`each egress edge unit 120, a DWDM receiver 131 can receive
`various µAs from switch fabric 135 that have been directed
`from each ingress edge unit 110 to the receiving egress edge
`unit 120. The DWDM receiver 131 can demultiplex each µA
`and generate a separate optical stream for each wavelength
`that was present in the DWDM lambda count. Egress TWDM
`converter 132 can buffer each µA received and route the µAs to
`the destination egress port cards 126 according to the sched(cid:173)
`ule received from controller 140. The egress output port cards
`126 could then forward the data to external components in the
`optical network. Additionally, if a classification index was
`included in the overhead of the data packet, egress edge unit
`120 can read the classification index to determine routing
`information, quality of service processing, etc. However, it
`should be noted that reading the classification index can be
`done with simplistic table reading hardware/software, and
`does not require that the data packet actually be reclassified at
`
`
`
`Case 1:20-cv-07529 Document 1-8 Filed 09/14/20 Page 14 of 23
`
`US 8,116,315 B2
`
`5
`
`5
`egress edge unit 120. The classification parameters are used to
`implement QoS handling in the egress ports 126.
`As can be understood from the foregoing discussion,
`ingress edge unit 110 can determine a set of classification
`parameters, which can include a destination egress edge unit,
`a destination egress port, and QoS parameters for each incom(cid:173)
`ing data packet. These classification parameters can be used
`by controller 140 to schedule the transmission of data packets
`to the destination egress edge unit, and, additionally, the
`transmission of data packets within the destination egress
`edge unit to the destination egress interface port. Because the
`routing of a data packet to the egress edge port can be con(cid:173)
`trolled externally to the egress edge unit based on classifica(cid:173)
`tion parameter determined at the ingress edge unit, data pack(cid:173)
`ets do not have to be reclassified at the egress edge unit.
`Therefore, duplicative classification hardware and software
`can be eliminated.
`The discussion accompanying FIG. 1 described an exem(cid:173)
`plary embodiment ofrouter 100. However, it should be under(cid:173)
`stood that the present invention can be utilized to classify data 20
`packets at an ingress edge unit, without reclassification at the
`egress edge unit, in many configurations of optical routers or
`switches in an optical network.
`FIG. 2 is a diagrammatic representation of a second
`embodiment of a router 200 that can perform data packet
`classification at the ingress edge unit according to the present
`invention. Router 200 can include one or more ingress edge
`units 210, one or more egress edge units 220 and a optical
`switch core 230 for routing data packets between an ingress
`edge unit 210 and an egress edge unit 220 that can comprise
`an optical switch fabric 235 and a controller 240. While, for
`the sake of simplicity, the ingress and egress edge units are
`shown separately in FIG. 2, it should be understood the com(cid:173)
`bined edge units can be constructed with an ingress edge unit
`and an egress edge unit in a single physical edge unit. Each
`ingress edge unit 210 and each egress edge unit 220 can
`contain many ingress and egress ports of different types,
`respectively, that can connect to a range of other optical
`network elements, such as switches, routers, cross-connects,
`and/or transmission equipment. Additionally, optical switch
`core 230 can comprise a single switch core or alternatively,
`can comprise a stack of switch cores or a multiple plane
`switch core.
`For the sake of explanation, Router 200 could have 16
`ingress edge units (labeled Il,I2, I3 ... 116) and 16 egress
`edge units (labeled El, E2, E3 ... El 6). Each edge unit could
`have 16 OC-192 ports that use packet over SO NET to connect
`to other network elements. Each ingress edge unit 210 and
`each egress edge unit 220 can be connected to optical switch
`core 230 using WDM links with 16A (16 ports) running at 10
`Gbps for an aggregate of 265 Gbps. Each ingress edge unit
`can connect to switch fabric 235 via Ingress packet links 217
`while Egress edge units can connect to switch fabric 235 via
`egress packet links 227. Additionally, ingress and egress edge
`units can exchange control information with controller 240
`via ingress control links 219 and egress control links 229,
`respectively. The router illustrated in FIG. 2 is exemplary
`only and other router configurations, combinations of ingress
`and egress edge units, data rates and ports are possible. For a
`more detailed explanation of one embodiment of router 200
`that can be used in conjunction with the present invention, see
`U.S. patent application Ser. No. 09/698,666, entitled "A Non(cid:173)
`blocking Scalable Optical Router Architecture and Method
`for Routing Optical Traffic," incorporated by reference in its
`entirety.
`In one embodiment of the present invention, router 200 can
`receive data packets from an ingress interface port 215. The
`
`6
`data packets can be routed through ingress edge unit 210 to
`optical switch core 230 via an ingress edge unit output port
`253. Egress edge u