(12) United States Patent
`Miller et al.
`
`US006247058B1
`US 6,247,058 B1
`Jun. 12, 2001
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR
`PROCESSING NETWORK PACKETS USING
`TIME STAMPS
`
`Primary Examiner—Mark H. Rinehart
`Assistant Examiner—Paul Kang
`(74) Attorney, Agent, or Firm—David A. Plettner
`
`(75) Inventors: John P. Miller, Rocklin; Erik E.
`Erlandson, Roseville, both of CA (US)
`
`(73) Assignee; ?ewktppackard Company, P2110 Alto,
`CA (US)
`
`( * ) NOtiCeI
`
`Subject t0 any disclaimer, the term Of this
`Patent is extended or adjusted under 35
`U-S~C~ 154(k)) by 0 days-
`
`(21) Appl. No.: 09/050,645
`_
`Mar‘ 30’ 1998
`(22) Flled:
`(51) Int. CI.7 ....................... .. G06F 15/16; G06F 15/173;
`H04L 12/56
`(52) US. Cl. ........................ .. 709/234; 709/235; 709/240;
`370/418; 370/429; 710/53; 710/54; 702/187
`(58) Field of Search ................................... .. 709/234 235
`709/240 370/418 429 230 7106; 54?
`’
`’
`’
`’
`7027187’
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4 79 9 215 * 1/1989 Suziki '
`53907299 * 2/1995 Rege et al. ......................... .. 709/234
`5Z4O2Z417 * 3/1995 Aramaki_
`5,781,549 * 7/1998 Dai _
`5,926,458 * 7/1999 Yin ..................................... .. 370/230
`5,978,928 * 11/1999 Rust ......... ..
`702/187
`709/234
`5,991,812 * 11/1999 Srinivasan ---- -
`370/230
`67011775 * 1/2000 Bonomi et e1~
`6,026,074 * 2/2000 Stadler et al. ..................... .. 370/230
`
`(57)
`
`ABSTRACT
`_
`_
`A network device receives packets from a ?rst network
`segment, time stamps the packets as they arrive, and trans
`mits the packets to a second network segment. By time
`stamping packets as they arrive, stale packets can be iden
`ti?ed and discarded. A stale packet is a packet that has been
`pending in the network device longer than an active timeout
`interval, which may be varied based on network traf?c levels
`to conserve network bandwidth. Packets may also be dis
`carded to conserve packet buffer memory in the network
`device. For example, when an incoming packet arrives and
`an output buffer in which the packet must be stored is full,
`the Output buffer is scanned to identify and discard packets
`that have exceeded a minimum timeout interval, thereby
`allowing the ineeming Peeket ‘0 be Stored in the Output
`buffer. Many network protocols initiate ‘the retransmission of
`Packets after a “mom mterval has explred and an .aeknorl
`edge packet has not been received. The present invention
`conserves network bandwidth by not transmitting stale pack
`ets that either will be ignored or redundant when network
`traffic becomes heavy. The present invention also conserves
`buffer memory by allowing broadcast and multicast packets
`to be stored in and transmitted from a single broadcast
`packet output buffer. The proper packet'transmissi'on order at
`each Port 15 mamtamed by Companng the “me Stamp
`assigned to the broadcast packet when it arrived at the
`network device with the time stamps of the other packets in
`the Output buffer. Finally, the present invention provides
`many opportunities for collecting statistics, such as the
`average latency, mean latency and standard deviation of the
`latency of packets processed by network device.
`
`* cited by examiner
`
`15 Claims, 10 Drawing Sheets
`
`8Q?‘
`
`OUT-OF—BAND
`sTATIsnps PORT
`\105
`
`100x
`
`'
`
`FORWARDING
`
`, TIMEEITTAMP
`‘El
`9°\+—— we
`
`88)
`
`+
`
`94
`,/
`
`102
`
`UNIT
`
`104
`
`f
`STATISTICS 4
`UNIT
`A
`
`OUTPUT
`BUFFER
`0
`
`OUTPUT
`BUFFER
`1
`
`OUTPUT
`BUFFER
`4 ‘ N_2
`
`OUTPUT
`BUFFER
`N-1
`
`4
`
`OUTPUT CONTROL
`
`L
`
`UNIT
`
`92) J
`
`v
`OUT
`
`IN
`
`v
`OUT
`
`IN
`
`PORT 0
`
`PORT 1
`
`v
`OUT
`
`IN
`
`v
`OUT
`
`IN
`
`PORT N-2
`
`PORT N-1
`
`JUNIPER Ex 1016-pg. 1
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 1 0f 10
`
`US 6,247,058 B1
`
`APPLICATION
`
`24 J @
`
`PRESENTATION
`
`22/ @
`
`SESSION
`
`20 J 3
`
`TRANSPORT
`
`18 J @
`
`NETWORK
`
`16 J 1;
`
`DATA LINK
`
`14 J i
`
`HARDWARE
`
`12 J
`
`J
`10
`
`FIG.1
`(PRIORART)
`
`JUNIPER Ex 1016-pg. 2
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 2 of 10
`
`1B
`
`/ / /
`
`/
`
`/
`
`,\,2,\,\,\,\\/\,\\/E\/E\mmm+<mnm_m\mm:_._\/\/\\//\\//\\
`
`ll
`
`wmm5om
`
`
`
`>mcum:wwm_5om
`
`5:<u_m_om<mmooz
`
`m><>>mP<o
`
`wm_oo_mm_\wm_:o:>>w
`
`_u_,_.
`
`\/\\\/\\
`
`//I,.
`
`___
`
`%.E<moi“:W,N.u._~=..0_u_M,36\\//\\//mm\\//2‘W/\S\8x\U\\\////\\\\///\
`\\\//fl
`
`/\\//\ln|||IEHE,,mm_oozvEo>>Ez__
`
`JUNIPER Ex 1016-pg. 3
`
`JUNIPER Ex 1016-pg. 3
`
`

`
`U.S. Patent
`
`m
`
`10m.
`
`0hS
`
`US 6,247,058 B1
`
`2,:23M.0z_0m_<>>m0“_
`
`m72~-z_‘oM~_mu:3mmm_u:3mmm&3m_
`
`
`mm&3m_wSE30SE30SE30SE30
`
`z_._..:_OZ_.50.50z_._.DOZ_
`
`
`
`E"_<m_0_m...=
`
`_.-Z._.m_On_~-z._.mOn_Mmm=..0_u__\._.w_Omo._.m_On_
`
`JUNIPER Ex 1016-pg. 4
`
`JUNIPER Ex 1016-pg. 4
`
`

`
`U.S. Patent
`
`1
`
`1
`
`%
`
`f
`
`US 6,247,058 B1
`
`QZ<m-u_O-._.DO
`
`
`
`._.w_On_mofimfifim
`
`mX:J«S
`
`W:2:EM,mo_5:<B
`
`2:
`
`oz_am<>>mou_
`
`:2:
`
`m72N-z
`
`.mEv_o<n_5<oo<omm_
`
`
`
`
`
`mmrmam4H3350._.Dn:.DOmmtnm53:0._.:n_._.:O._.3n_._.:O
`omm_u_u5m_m_m_n_u_:mmmnmzm
`
`
`
`
`
`._oEzoo._.Dn_._.DO
`
`:2:
`
`z_.50z_.50.50z_.50z_
`
`72Eon«-2Eon._.mmawmVEon.o._.mon_
`
`JUNIPER Ex 1016-pg. 5
`
`JUNIPER Ex 1016-pg. 5
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 5 0f 10
`
`US 6,247,058 B1
`
`WAIT FOR FIRST BIT OF
`108
`INCOMING PACKET, GET TIME
`-—V STAMP VALUE FROM CLOCK
`106, RECEIVE REMAINDER OF
`PACKET
`
`110
`
`IS PACKET
`A BROADCAST
`PACKET?
`
`DESTINATION OUTPUT
`
`114
`
`SAVE PACKET IN
`DESTINATION OUTPUT
`BUFFER ALONG WITH TIME
`STAMP AND TIMEOUT
`INTERVAL
`
`116
`
`CALL STALE PACKET
`REMOVAL SUBROUTINE 144
`
`118
`
`IS DESTINATION
`OUTPUT BUFFER STILL
`FULL?
`
`NO
`
`DISCARD RECEIVED
`PAC KET
`
`107
`
`FIG. 5
`
`JUNIPER Ex 1016-pg. 6
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 6 0f 10
`
`US 6,247,058 B1
`
`IS
`BROADCAST PACKET
`OUTPUT BUFFER 98
`FULL?
`
`124
`
`132 \
`CALL STALE
`BROADCAST PACKET
`REMOVAL
`SUBROUTINE 168
`
`SAVE BROADCAST PACKET IN
`BROADCAST PACKET OUTPUT
`BUFFER 98 ALONG WITH TIME
`STAMP, AND A COUNTER VALUE
`INDICATING NUMBER OF OUTPUT
`BUFFERS IN WHICH A BROADCAST
`PACKET TAG WILL BE STORED OR
`A LIST OF PORT IDs INDICATING
`THE PORTS ASSOCIATED WITH
`THE OUTPUT BUFFERS
`
`134
`
`126
`
`IS
`BROADCAST PACKET
`OUTPUT BUFFER 98
`STILL FULL?
`
`ARE ANY
`DESTINATION OUTPUT
`BUFFERS FULL?
`
`YES
`
`128
`
`SAVE BROADCAST PACKET
`_> TAG AND ACTIVE TIMEOUT
`INTERVAL IN EACH OUTPUT
`BUFFER THAT IS NOT FULL
`
`é \ 130
`
`NO
`
`DISCARD RECEIVED
`BROADCAST PACKET
`
`\136 A CALL STALE PACKET
`
`REMOVAL SUBROUTINE 144
`FOR FULL OUTPUT BUFFERS
`
`K 138
`
`ARE
`ANY DESTINATION
`OUTPUT BUFFER STIL
`FULL?
`
`140
`
`142
`
`107
`
`FIG. 6
`
`SUBTRACT NUMBER OF FULL OUTPUT
`BUFFERS FROM COUNTER VALUE OR
`REMOVE PORT IDS OF FULL OUTPUT
`BUFFER FROM LIST OF PORT IDS
`
`JUNIPER Ex 1016-pg. 7
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 7 0f 10
`
`US 6,247,058 B1
`
`146
`
`SCAN ENTRIES IN OUTPUT
`BUFFER COMPARING TIME
`STAMP TO CLOCK 106
`
`HAVE ANY,
`ENTRIES REACHED MINIMUM
`TIMEOUT INTERVAL?
`
`IDENTIFY OLDEST ENTRY
`
`158 J REMOvE OLDEST
`—> BROADCAST PACKET TAG
`FROM OUTPUT BUFFER
`+
`DECREMENT COUNTER
`VALUE OF CORRESPONDING
`BROADCAST PACKET IN
`BROADCAST PACKET
`OUTPUT BUFFER 98 OR
`REMOVE PORT ID FROM LIST
`OF PORT IDS
`
`160 /
`NO
`
`OUNTER VALU
`zERO OR IS THIS THE
`LAST PORT
`ID?
`
`162
`
`OLDEST ENTRY A
`BROADCAST PACKET
`TAG?
`
`REMOvE BROADCAST
`PACKET FROM BROADCAST
`PACKET OUTPUT BUFFER 98
`
`164 j
`
`REMOVE OLDEST PACKET
`FROM OUTPUT BUFFER
`
`156 1
`
`END SUBROUTINE -
`RETURN TO CALLING
`PROGRAM
`
`Y
`
`'6
`144
`
`FIG. 7
`
`JUNIPER Ex 1016-pg. 8
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 8 0f 10
`
`US 6,247,058 B1
`
`START
`
`170
`
`FOR EACH ENTRY IN
`BROADCAST PACKET
`OUTPUT BUFFER 98, SCAN
`ALL BROADCAST PACKET
`TAGS IN ALL OUTPUT
`BUFFERS AND COMPARE
`TIME STAMPS TO CLOCK 106
`
`HAVE ALL
`BROADCAST BUFFER TAGS
`EXCEEDED REACHED MINIMUM
`TIMEOUT INTERVAL FOR
`ANY BROADCAST
`PACKETS?
`
`NO
`
`REMOVE FROM ALL OUTPUT
`BUFFERS THE BROADCAST
`PACKET TAGS
`CORRESPONDING TO THE
`OLDEST TlMED-OUT \
`BROADCAST PACKET
`176
`
`I
`
`REMOVE OLDEST
`BROADCAST PACKET FROM
`BROADCAST PACKET
`OUTPUT BUFFER 9a
`
`\178
`
`END SUBROUTINE -
`RETURN TO CALLING
`PROGRAM
`
`168
`
`180
`
`FIG. 8
`
`JUNIPER Ex 1016-pg. 9
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 9 0f 10
`
`US 6,247,058 B1
`
`V
`WAIT UNTIL NETWORK SEGMENT IS READY TO <_®
`RECEIVE A TRANSMITTED PACKET
`I
`\184
`SCAN ENTRIES IN OUTPUT BUFFER TO FIND
`OLDEST TIME STAMP
`
`\ 186
`
`YES
`
`IS OLDEST
`ENTRY A BROADCAST
`PACKET TAG?
`
`188
`
`COMPARE TIME STAMP OF
`PACKET TO CLOCK 106
`
`AS PACKE
`REACHED ACTIVE
`TIMEDOUT
`INTERVAL?
`
`192
`
`DISCARD PACKET
`
`\ 200
`
`ATTEMPT TO TRANSMIT
`PACKET
`
`\-194
`
`DID
`A COLLISION
`OCCUR?
`
`YES
`
`DID PACKET
`TRANSMIT
`UCCESSFULLY
`
`195
`
`196
`
`REMOVE PACKET FROM
`OUTPUT BUFFER \ 198
`
`182
`
`FIG. 9
`
`JUNIPER Ex 1016-pg. 10
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 10 0f 10
`
`US 6,247,058 B1
`
`COMPARE TIME STAMP OF
`BROADCAST PACKET TO
`CLOCK 106
`
`K
`202
`
`HAS
`BROADCAST PACKET
`REACHED ACTIVE TIMEOUT
`INTERVAL?
`
`204
`
`L) Bggi‘ggfg
`PACKET TAG
`\
`216
`
`YES
`
`206
`
`ATTEMPT TO TRANSMIT
`BROADCAST PACKET
`
`DID A
`COLLISION
`
`207
`
`PACKET TRANSMIT
`SUCCESSFULLY?
`
`DECREMENT COUNTER VALUE OF
`BROADCAST PACKET IN BROADCAST
`PACKET OUTPUT BUFFER 98 OR (—————‘
`REMOVE PORT ID FROM LIST OF PORT
`IDs
`
`\ 210
`
`IS
`OUNTER VALUE ZER
`OR IS THIS THE LAST
`PORT ID?
`
`YES
`
`REMOVE BROADCAST
`PACKET FROM BROADCAST
`PACKET OUTPUT BUFFER 98
`
`JUNIPER Ex 1016-pg. 11
`
`

`
`US 6,247,058 B1
`
`1
`METHOD AND APPARATUS FOR
`PROCESSING NETWORK PACKETS USING
`TIME STAMPS
`
`FIELD OF THE INVENTION
`
`The present invention relates to communication betWeen
`network nodes. More speci?cally, the present invention
`relates a netWork device that transmits data packets betWeen
`netWork segments and time stamps arriving packets to
`support a variety of packet management functions.
`
`DESCRIPTION OF THE RELATED ART
`
`10
`
`15
`
`In the art of computer networking, protocol stacks are
`commonly used to transmit data betWeen netWork nodes that
`are coupled by netWork media. NetWork nodes include
`devices such as computer Workstations, servers, netWork
`printers, netWork scanners, and the like. To harmoniZe the
`development and implementation of protocol stacks, the
`International Standards OrganiZation (ISO) promulgated an
`Open System Interconnection (OSI) Reference Model that
`prescribes seven layers of netWork protocols.
`FIG. 1 is a block diagram 10 of the OSI Reference Model.
`The model includes a hardWare layer 12, a data link layer 14,
`a netWork layer 16, a transport layer 18, a session layer 20,
`a presentation layer 22, and an application layer 24. Each
`layer is responsible for performing a particular task. Hard
`Ware layer 12 is responsible for handling both the mechani
`cal and electrical details of the physical transmission of a bit
`stream. Data link layer 14 is responsible for handling the
`packets, including generating and decoding of the address
`used by the hardWare protocol and any error detection and
`recovery that occurred in the physical layer. For example, in
`an Ethernet netWork data link layer 14 is responsible for
`generating and decoding the media access control (MAC)
`address. NetWork layer 16 is responsible for providing
`connections and routing packets in the communication
`netWork, including generating and decoding the address
`used by upper level protocols and maintaining routing
`information for proper response to changing loads. For
`example, in the TCP/IP protocol, netWork layer 16 is respon
`sible for generating and decoding the IP address. Transport
`layer 18 is responsible for end-to-end connections betWeen
`nodes in the netWork and the transfer of messages betWeen
`the users, including partitioning messages into packets,
`maintaining packet order and delivery, ?oW control, and
`physical address generation. Session layer 20 is responsible
`for implementing the process-to-process protocols. Presen
`tation layer 22 is responsible for resolving the differences in
`formats among the various sites in the netWork, including
`character conversions, and duplex (echoing). Finally, appli
`cation layer 24 is responsible for interacting directly With the
`users. Layer 24 may include applications such as electronic
`mail, distributed data bases, Web broWsers, and the like.
`Before the ISO promulgated the OSI Reference Model,
`the Defense Advanced Research Projects Agency (DARPA)
`promulgated the ARPNET Reference Model. The ARPNET
`reference model includes four layers, a netWork hardWare
`layer, a netWork interface layer, a host-to-host layer, and a
`process/application layer.
`As their names imply, the OSI and ARPNET Reference
`Models provide guidelines that designers of protocols may
`or may not choose to folloW. HoWever, most netWorking
`protocols de?ne layers that at least loosely correspond to a
`reference model.
`In the ?eld of computing, there are many popular proto
`cols used to transmit data betWeen netWork nodes. For
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`2
`example, TCP/IP, AppleTalk®, NetBEUI, and IPX are all
`popular protocols that are used to transmit data betWeen
`servers, Workstations, printers, and other devices that are
`coupled to computer netWorks.
`It is common for several protocols to operate concurrently
`Within a single netWork node, even if the netWork node has
`a single netWork interface. For example, a typical computer
`Workstation may use TCP/IP to communicate over the
`Internet, and IPX to communicate With a netWork server.
`LikeWise, a printer may be con?gured to receive print jobs
`using either the AppleTalk® protocol or the NetBEUI pro
`tocol. Typically these protocols sit on top of loWer level
`hardWare protocols. For example, it is common for tWo
`computer systems coupled via an Ethernet netWork to com
`municate using the TCP/IP protocol. Generally, a softWare
`routine existing at data link layer 14 or netWork layer 16
`routes data packets betWeen the netWork adapter and the
`proper protocol stack.
`Consider a TCP/IP packet transmitted over an Ethernet
`netWork. The Ethernet packet includes a 48-bit media access
`control (MAC) address that addresses another node on the
`Ethernet netWork. The entire Ethernet packet is protected by
`a cyclic redundancy check (CRC) code that is calculated and
`stuffed into the Ethernet packet by the sending netWork
`adapter, and is used by the receiving netWork adapter to
`verify the integrity of the Ethernet packet. If the integrity of
`the packet cannot be veri?ed, the packet is discarded.
`Encapsulated Within the Ethernet packet is the IP portion of
`the TCP/IP protocol, Which is knoWn in the art as a data
`gram. The datagram includes a 32-bit IP address and a 16 bit
`checksum code that protects the IP header. If the integrity of
`the IP header cannot be veri?ed, the datagram is discarded.
`The TCP portion of the TCP/IP protocol is encapsulated
`Within the datagram, and has a 16 bit checksum code that
`protects the TCP header and the contents of the TCP portion
`of the datagram. If the integrity of the TCP header or the
`contents of the TCP portion cannot be veri?ed, the datagram
`is discarded and the sender Will retransmit the packet after
`not receiving an acknoWledge datagram from the intended
`recipient. Note that this packet contains tWo addresses, the
`Ethernet address and the IP address. The relationship
`betWeen these tWo addresses Will be described in greater
`detail beloW.
`FIG. 2 is a diagram shoWing a prior art netWork 26.
`NetWork 26 interconnects netWork nodes 28, 30, 32, 34, 36,
`38, 40, 42, and 44. As described above, the netWork nodes
`may be devices such as computer Workstations, servers,
`netWork printers, netWork scanners, and the like. For the
`sake of this discussion, assume that the netWork nodes are
`equipped With Ethernet netWork adapters and transmit data
`using the TCP/IP protocol. Many netWorks conform to a
`series of standards promulgated by the Institute of Electrical
`and Electronics Engineers
`This series of standards is
`knoWn in the art as the IEEE 802 family of standards. The
`IEEE 802 family of standards are hereby incorporated by
`reference.
`The netWork nodes are coupled together into LAN seg
`ments via hubs. All nodes in a LAN segment are in a
`common collision domain because each node in a LAN
`segment receives a signal When another node attempts to
`transmit a packet, and if tWo nodes in a LAN segment
`attempt to transmit a packet at the same time, a collision
`occurs. The Ethernet protocol includes a retransmission
`algorithm that minimiZes the likelihood that another colli
`sion Will occur When the tWo nodes attempt to retransmit
`their respective packets. In FIG. 2, netWork nodes 28, 30,
`and 32 are coupled together into LAN segment 48 via hub
`
`JUNIPER Ex 1016-pg. 12
`
`

`
`US 6,247,058 B1
`
`10
`
`15
`
`25
`
`3
`46. Likewise, network nodes 34, 36, and 38 are coupled
`together into LAN segment 52 via hub 50 and network nodes
`40, 42, and 44 are coupled together into LAN segment 56 via
`hub 54.
`Traditionally, a prior art hub was a network device that
`served as the central location for attaching wires from
`network nodes, such as workstations. Early prior art hubs
`were passive. There was no ampli?cation of the network
`signals, and the hub simply coupled together the network
`wiring from the network nodes to form sets of common
`conductors that interconnected the nodes. On the other hand,
`repeaters provided ampli?cation of signals between network
`nodes, thereby allowing a larger number of network nodes to
`be coupled together into LAN segments. More recently,
`hubs have begun to incorporate some of the functionality of
`switches (discussed in greater detail below) and repeaters.
`Modern hubs are capable of implementing multiple sub
`networks such that two or more network nodes coupled to a
`hub can send and receive data simultaneously. In addition,
`modern hubs are capable of scrambling signals such that
`only the network node addressed by a packet receives an
`unscrambled version of the packet. However, in general
`modern hubs maintain the appearance, from the point of
`view of the network nodes, of a single set of conductors
`connecting all network nodes of the LAN segment. Hubs
`and repeaters typically exist within hardware layer 12 of OSI
`Reference Model 10 of FIG. 1.
`Switches and bridges are used to interconnect local or
`remote LAN segments. Switches and bridges form a single
`logical network, and operate at data link layer 14 and
`hardware layer 12 of OSI Reference Model 10. In FIG. 2,
`switch 58 connects sub-networks 48 and 52. In the Ethernet
`protocol, packets are addressed by a media access control
`(MAC) address. Switches and bridges maintain lists of the
`MAC address of the network nodes of each LAN segment to
`35
`which they are attached, and forward packets between LAN
`segments as appropriate.
`While switches and bridges link together LAN segments
`to form subnets, routers are used to link together subnets via
`another network, such as the Internet or a wide area network
`Routers may also be used to route packets within a
`common subnet. Routers maintain tables that associate
`higher level protocol addresses (such as an IP address) with
`ports of the router. In contrast to switches and bridges,
`routers are also capable of viewing the network as a hier
`archical topology, wherein large blocks and ranges of
`address are routed to other routers for further routing. For
`this reason, routers are often used to route packets in very
`large networks, such as the Internet.
`A default gateway is the router to which a node routes a
`packet when the node cannot determine that an outgoing
`packet is addressed to a node on the same subnet. Apacket
`transmitted to a default gateway may be processed by
`several other routers before arriving at the destination node.
`Consider that network node 40 seeks to send a TCP/IP
`packet to network node 28. Further assume that a substantial
`distance separates sub-networks 56 and 48. The packet is
`?rst transmitted to switch 60 and then to router 64, which is
`the default gateway used by node 40. Router 64 in turn
`transmits the packet to the Internet, which is represented by
`dotted line 70. Router 69 routes the packet to router 68 via
`backbone connection 72, which may include additional
`routers. Router 68 transmits the packet to router 62, which
`in turn routes the packet to switch 58. Switch 58 recogniZes
`that the network node addressed by the packet exits in LAN
`segment 48 and forwards the packet to that LAN segment
`where network node 28 receives the packet.
`
`45
`
`55
`
`65
`
`4
`One characteristic of most network transmission proto
`cols is that delivery of the packet is assured by upper levels
`of the protocol. In the example above, the TCP layer of the
`protocol stack in network node 28 transmits an acknowledge
`packet after the packet is received. If the TCP layer of the
`protocol stack of node 40 does not receive the acknowledge
`packet before a timeout interval has expired, node 40
`retransmits the packet and waits for another acknowledge
`packet. Other protocols de?ne different acknowledgment
`schemes. For example, some protocols send a single
`acknowledge packet acknowledging reception of a group of
`packets.
`Many factors can cause a packet to not be received. For
`example, assume that network traf?c is heavy within LAN
`segment 48. The packet may have to wait at switch 58 until
`LAN segment 48 may receive the packet, and the delay in
`transmitting the packet may exceed the timeout interval of
`the TCP/IP protocol. In addition, if the buffers of switch 58
`that store packets become full, received packets may have to
`be discarded.
`An unfortunate consequence of requesting retransmission
`when packets timeout is that additional network bandwidth
`is required to transmit the same information when network
`traffic is heavy compared to when network traf?c is light.
`Accordingly, many protocols will ?ood a network with
`additional packets at a time when the network is least able
`to handle additional traffic.
`
`SUMMARY OF THE INVENTION
`The present invention is a network device that receives
`packets from a ?rst network segment, time stamps the
`packets as they arrive, and transmits the packets to a second
`network segment. The time stamps are used to support a
`variety of packet and memory management functions.
`By time stamping packets as they arrive, stale packets can
`be identi?ed and discarded. A stale packet is a packet that
`has been pending in the network device longer than an active
`timeout interval. The present invention allows the active
`timeout interval to be varied based on network congestion,
`thereby conserving network bandwidth, and conserves
`packet buffer memory by allowing incoming packets to be
`stored in a buffer if the buffer is full and packets have
`exceeded a minimum timeout interval. With respect to
`conserving packet buffer memory, when an incoming packet
`arrives and an output buffer in which the packet must be
`stored is full, the output buffer is scanned to identify packets
`exceeding the minimum timeout value. One or more of the
`oldest packets which are at least as old as the minimum
`timeout interval are discarded, thereby allowing the incom
`ing packet to be stored in the output buffer. With respect to
`conserving network bandwidth, stale outbound packets that
`are otherwise eligible to be transmitted may be discarded if
`the age of the packet has exceeded the active timeout
`interval. A network device in accordance with the present
`invention may select a longer active timeout interval when
`network traffic is light and redundant retransmission will not
`cause a network to approach the upper limit of the network’s
`bandwidth. When network traffic is heavy, the active timeout
`interval may be lowered toward the minimum timeout
`interval, thereby conserving network bandwidth. Many net
`work protocols initiate the retransmission packets after a
`timeout interval has expired and an acknowledge packet has
`not been received. The present invention conserves network
`bandwidth by not transmitting stale packets that will either
`be ignored or will be redundantly retransmitted.
`Another feature provided by the present invention is that
`broadcast and multicast packets can be stored in and trans
`
`JUNIPER Ex 1016-pg. 13
`
`

`
`US 6,247,058 B1
`
`5
`mitted from a single broadcast packet output buffer. In the
`prior art, broadcast and multicast packets Were often copied
`to all the output buffers associated With the ports to Which
`the packet Was being transmitted. In accordance With the
`present invention, broadcast and multicast packets are stored
`in the broadcast packet output buffer and a much smaller
`broadcast packet tag is stored in the output buffer associated
`With each port. The time stamp assigned to the broadcast or
`multicast packet When it arrived at the netWork device is
`used to determine the transmission order at each port by
`comparing the broadcast or multicast packet time stamp With
`the time stamps of the other packets in the output buffer.
`Accordingly, the present invention enhances the efficient use
`of buffer memory.
`Finally, the present invention provides many opportuni
`ties for collecting statistics, such as the average latency,
`mean latency and standard deviation of the latency of
`packets processed by netWork devices. Such statistics can be
`extremely helpful to a netWork administrator troubleshoot
`ing a netWork problem.
`
`10
`
`15
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of the Open System Intercon
`nection (OSI) Reference Model.
`FIG. 2 is a diagram shoWing a prior art netWork.
`FIG. 3 is a block diagram of a prior art N port netWork
`device.
`FIG. 4 is a block diagram of an N port netWork device in
`accordance With the present invention.
`FIGS. 5 and 6, taken together, are a ?oWchart illustrating
`hoW incoming packets are processed by the N port netWork
`device of FIG. 4.
`FIGS. 7 and 8 are ?oWcharts illustrating subroutines that
`remove stale packets.
`FIGS. 9 and 10, taken together, are a ?oWchart illustrating
`hoW outbound packets are processed by the N port netWork
`device of FIG. 4.
`
`25
`
`35
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`6
`connected via coaxial cable, the input and output lines are
`formed by common conductors.
`When a packet is received at device 74, the packet is
`processed by forWarding unit 76. ForWarding unit 76
`decodes the address of the packet and determines the port (or
`ports) to Which the packet should be forWarded. Outgoing
`packets are placed in the output buffer of the port to Which
`they are being forWarded. Many protocols de?ne a format
`for broadcast packets, Wherein a single packet is replicated
`and sent to all netWork nodes on a netWork. In the case of
`a broadcast packet, the outgoing packet is transmitted to the
`output buffers of all ports. The output buffers are simple
`?rst-in ?rst-out (FIFO) buffers, With the oldest packet in
`each buffer being transmitted as soon as the netWork seg
`ment is able to accept the packet. When an output buffer is
`full, incoming packets are discarded.
`The American National Standards Institute (ANSI) and
`Institute for Electrical and Electronics Engineers (IEEE)
`have promulgated ANSI/IEEE Standard 802.1D, Which Was
`incorporated above by reference along With the other mem
`bers of the IEEE 802 family of standards. This standard
`relates to bridges and de?nes several relevant parameters:
`2.3.6 Frame Lifetime. The service provided by the MAC
`Sublayer ensures that there is an upper bound to the
`transit delay experienced for a particular instance of
`communication. This maximum frame lifetime is nec
`essary to ensure the correct operation of higher layer
`protocols. The additional transit delay introduced by a
`Bridge is discussed above.
`To enforce the maximum frame lifetime a Bridge may be
`required to discard frames. Since the information pro
`vided by the MAC Sublayer to a Bridge does not
`include the transit delay already experienced by any
`particular frame, Bridges must discard frames to
`enforce a maximum delay in each Bridge.
`The value of the maximum bridge transit delay is based on
`both the maximum delays imposed by all the Bridges in
`the Bridged Local Area NetWork and the desired maxi
`mum frame lifetime. A recommended and an absolute
`maximum value are speci?ed in Table 4-2 [of the
`802.1D Standard].
`3.7.3 Queued Frames. The ForWarding Process provides
`storage for queued frames, aWaiting an opportunity to
`submit these for transmission to the individual MAC
`Entities associated With each Bridge Port. The order of
`queued frames shall be maintained.
`A frame queued by the ForWarding Process for transmis
`sion on a Port shall be removed from that queue on
`submission to the individual MAC Entity for that Port;
`no further attempt shall be made to transmit the frame
`on that Port even if the transmission is knoWn to have
`failed.
`A frame queued by the ForWarding Process for transmis
`sion on a Port can be removed from that queue, and not
`subsequently transmitted, if the time for Which buffer
`ing is guaranteed has been exceeded for that frame.
`A frame queued for transmission on a Port shall be
`removed from that queue, and not subsequently sub
`mitted to the individual MAC Entity for that Port, if
`that is necessary to ensure that the maximum bridge
`transit delay (2.3.6) Will not be exceeded at the time at
`Which the frame Would be subsequently transmitted.
`A frame queued for transmission on a Port shall be
`removed from that queue if the associated Port leaves
`the ForWarding state.
`
`The present invention is a netWork device, such as a
`sWitch, bridge, router, sWitching hub, and the like, that time
`stamps arriving packets to facilitate a variety of functions,
`such as dropping stale packets, processing broadcast
`packets, and collecting latency statistics. Before discussing
`the present invention in detail, consider prior art N port
`netWork device 74 shoWn in FIG. 3. Device 74 includes
`forWarding unit 76, and an output buffer for each port, such
`as output buffers 78, 80, 82, and 84. Device 74 represents
`any type of netWork device that receives a packet from a
`source netWork segment at one port, and forWards the packet
`to a destination netWork segment at another port, Wherein
`the latency of the transmission time is dependent upon the
`ability of the destination segment to receive the packet.
`Device 74 may be a sWitch, bridge, router, sWitching hub, or
`any similar device. For example, in FIG. 2 sWitch 58 is such
`a device, Wherein sWitch 58 can receive a packet via LAN
`segment 61, but cannot transmit the packet to LAN segment
`48 While LAN segment 48 is being used to transmit another
`packet, or because the netWork protocol has requested that
`transmission stop.
`In FIG. 3, device 74 has N ports. Although each port is
`shoWn as having an input line and an output line, those
`skilled in the art Will recogniZe that other con?gurations are
`possible. For example, in 10-Base-2 Ethernet networks
`
`45
`
`55
`
`65
`
`JUNIPER Ex 1016-pg. 14
`
`

`
`US 6,247,058 B1
`
`7
`Removal of a frame from a queue for transmission on any
`particular Port does not of itself imply that it shall be
`removed from a queue for transmission on any other
`Port.
`Table 4-2 of ANSI/IEEE Standard 802.1D indicates that
`the recommended value of the maximum bridge transit delay
`1.0 seconds, While the absolute maximum value is 4.0
`seconds.
`FIG. 4 is a block diagram of an N port netWork device 86
`in accordance With the present invention. Device 86 includes
`an output buffer for each port (such as output buffers 88, 90,
`92, and 94), an output control unit 96, a broadcast packet
`output buffer 98, and forwarding unit 100. ForWarding unit
`100 includes statistics unit 104 and time stamp unit 102.
`Finally, time stamp unit 102 includes clock 106.
`Incoming packets receive a time stamp as they arrive. The
`precision of clock 106, and the resulting time stamp, should
`be equal to or greater than the smallest time that is required
`to be measured, Which preferably is the time required to
`receive a single data bit. In addition, clock 106 and the
`resulting time stamp should be able to represent at least the
`longest timeout interval required, and preferably the “up
`time” of netWork device 86.
`As packets arrive and are assigned a time stamp, forWard
`ing unit 100 forWards the packets and associated time
`stamps to the appropriate output buffers. Output control unit
`96 monitors contents of the output buffers, and transmits
`packets that have not exceeded an active timeout interval,
`With the oldest packets being transmitted ?rst. Note that if
`device 86 is a bridge adhering to ANSI/IEEE Standard
`802.1D, the active timeout interval shall not exceed 4.0
`seconds. After a packet is transmitted, it is removed from the
`output buffer. The active