(12) United States Patent
`Miller et al.
`
`USOO6247058E31
`(10) Patent No.:
`US 6,247,058 B1
`(45) Date of Patent:
`Jun. 12, 2001
`
`(54) METHOD AND APPARATUS FOR
`PROCESSING NETWORK PACKETS USING
`TIME STAMPS
`(75) Inventors: John P. Miller, Rocklin; Erik E.
`Erlandson, Roseville, both of CA (US)
`(73) Assignee: Hewlett-Packard Company, Palo Alto,
`CA (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/050,645
`(22) Filed:
`Mar. 30, 1998
`(51) Int. Cl." ......................... G06F 15/16: G06F 15/173;
`HO4L 12/56
`(52) U.S. Cl. .......................... 709/234. 709/235. 709/240;
`370/418; 370/429; 710/53; 710/54; 702/187
`(58) Field of Search ..................................... 700,234,235,
`709/240; 370/418, 429, 230; 7053 54.
`s
`s
`s
`s
`702 s:
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,799,215 * 1/1989 Suziki,
`5,390,299
`2/1995 Rege et al... 700
`5.402,417
`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
`5.991,812 * 11/1999 Srinivasan ......
`... 709/234
`6,011,775 * 1/2000 Bonomi et al.
`... 370/230
`6,026,074
`2/2000 Stadler et al. ....................... 370/230
`* cited by examiner
`
`Primary Examiner Mark H. Rinehart
`Assistant Examiner Paul Kang
`(74) Attorney, Agent, or Firm-David A. Plettner
`(57)
`ABSTRACT
`A network device receives packets from a first 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
`tified 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 traffic 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 incoming packet to be stored in the output
`buffer. Many network protocols initiate the retransmission of
`packets after a timeout interval has expired and an acknowl
`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 transmission order at
`each port is maintained by comparing the time 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.
`
`15 Claims, 10 Drawing Sheets
`
`86
`Ya
`
`OUT-OF-BAND
`statises PORT
`sos
`
`100-
`
`--> FORWARDING --
`
`UNT
`
`104
`102
`?
`Y
`TMSIAMP STATISTICS -
`CLOCK
`UNI
`94
`106
`
`y
`
`88
`Y
`
`90
`Y
`
`OUTPUT
`BUFFER
`O
`
`OUTPUT
`BUFFER
`1
`
`BROACASTPACKET
`OUTPUTUFFER
`
`98
`
`OUTPUT
`BUFFER
`N-2
`
`OUTPUT
`BUFFER
`N-1
`
`|
`
`
`
`OUTPUCONROL
`
`UNIT
`
`
`
`v
`
`OUT
`N
`PORTO
`
`v
`
`OUT
`ORT1
`
`IN
`
`w
`
`IN
`OUT
`PORTN-2
`
`T
`
`IN
`OUT
`PORTN-1
`
`HPE 1031-0001
`
`HPE Co. v. ChriMar Sys., Inc.
`IPR Pet. - U.S. Patent No. 8,902,760
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 1 of 10
`
`US 6,247,058 B1
`
`24
`
`22
`
`18
`
`16
`
`14
`
`12
`
`DATA LINK
`
`f
`
`10
`
`FIG. 1
`(PRIOR ART)
`
`HPE 1031-0002
`
`

`

`U.S. Patent
`
`Jun.12, 2001
`
`Sheet 2 of 10
`
`US 6,247,058 BL
`
`\7~af“7
`
`Fe(ve
`
`ro a
`
`ZcL
`
`\Ea)SuaLNOw
`
`_LoSAVMALVD
`
`791inv43q0SVSHGON
`
`AdG48NSaainow
`
`ag6gSa9dING/SAHOLIMS
`
`//i!||\
`
`7“XN{/\
`oc~syvv\.99
`
`|!/\{\!\/\\PS,‘,vSWa
`\/\/——\i#|||I|
`eoTScGeoAOrme“ieoOif4\7\/\/\\/\1rt!1\!,\//\/\.0s/\|/SYA1VaAday/SANH
`NXYYanoe
`
`(LYVYOIMd)éJanols
`
`HPE 1031-0003
`
`HPE 1031-0003
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 3 of 10
`
`US 6,247,058 B1
`
`
`
`Z-N LÀ HOd
`
`LTTO
`
`€ ERIT,5)|=|
`
`
`
`(LHV HOTHd)
`
`L?IO
`
`?, LYHOd
`
`HPE 1031-0004
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 4 of 10
`
`US 6,247,058 B1
`
`
`
`TO?| LNO O LTld L?IO
`
`LINT)
`
`
`HPE 1031-0005
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 5 of 10
`
`US 6,247,058 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WAIT FOR FIRST BIT OF
`INCOMING PACKET, GET TIME
`STAMP VALUE FROM CLOCK
`106, RECEIVE REMAINDER OF
`PACKET
`
`IS PACKET
`A BROADCAST
`PACKETP
`
`DESTINATION OUTPUT
`
`YES
`
`SAVE PACKET IN
`DESTINATION OUTPUT
`BUFFER ALONG WITH TME
`STAMP AND TIMEOUT
`INTERVAL
`
`CALL STALE PACKET
`REMOVAL SUBROUTINE 144
`
`
`
`IS DESTINATION
`OUTPUT BUFFER STILL
`FULLP
`
`DISCARD RECEIVED
`PACKET
`
`
`
`107
`
`FIG. 5
`
`HPE 1031-0006
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 6 of 10
`
`US 6,247,058 B1
`
`
`
`132
`
`
`
`
`
`
`
`IS
`BROADCAST PACKET
`OUTPUT BUFFER 98
`FULL2
`
`CALL STALE
`BROADCAST PACKET
`REMOVAL
`SUBROUTINE 168
`
`
`
`
`
`
`
`SAVE BROADCAST PACKET IN
`BROADCAST PACKET OUTPUT
`BUFFER 98 ALONG WITH TIME
`STAMP, AND A COUNTERVALUE
`INDICATING NUMBER OF OUTPUT
`BUFFERS IN WHICH A BROADCAST
`PACKET AG WILL BE STORED OR
`A LIST OF PORT IDS INDICATING
`THE PORTS ASSOCATED WITH
`THE OUTPUT BUFFERS
`
`
`
`
`
`
`
`
`
`ARE ANY
`DESTINATION OUTPUT
`BUFFERS FULL2
`
`YES
`
`IS
`BROADCAST PACKET
`OUTPUT BUFFER 98
`STLL FULLP
`
`YES
`
`DISCARD RECEIVED
`BROADCAST PACKET
`
`126
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SAVE BROADCAST PACKET
`TAG AND ACTIVE TIMEOUT
`INTERVAL IN EACH OUTPUT
`BUFFER THAT IS NOT FULL
`
`CALL STALE PACKET
`REMOVAL SUBROUTINE 144
`FOR FULL OUTPUT BUFFERS
`
`ARE
`ANY DESTINATION
`OUTPUT BUFFERSTL
`FULLP
`
`SUBTRACT NUMBER OF FULL OUTPUT
`BUFFERS FROM COUNTERVALUE OR
`REMOVE PORT IDS OF FULL OUTPUT
`BUFFER FROM LIST OF PORT DS
`
`107
`
`
`
`FIG. 6
`
`HPE 1031-0007
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 7 of 10
`
`US 6,247,058 B1
`
`START
`
`146
`
`SCAN ENTRIES IN OUTPUT
`BUFFER COMPARING TIME
`STAMP TO CLOCK 106
`
`148
`
`
`
`
`
`
`
`HAVE ANY
`ENTRIES REACHEDMINIMUM
`TIMEOUT INTERVAL2
`
`IDENTFY OLDEST ENTRY
`
`
`
`
`
`158
`
`REMOVE OLDEST
`BROADCAST PACKETTAG
`FROM OUTPUT BUFFER
`
`DECREMENT COUNTER
`VALUE OF CORRESPONDING
`BROADCAST PACKET IN
`BROADCAST PACKET
`OUTPUT BUFFER 98 OR
`REMOVE PORT ID FROM LIST
`OF PORT DS
`
`OUNTERVALU
`ZERO OR IS THIS THE
`LAST PORT
`D?
`
`S
`OLDEST ENTRYA
`BROADCAST PACKET
`TAGT
`
`REMOVE BROADCAST
`PACKET FROM BROADCAST
`PACKET OUTPUT BUFFER 98
`
`
`
`REMOVE OLDEST PACKET
`FROM OUTPUT BUFFER
`
`END SUBROUTINE -
`RETURN TO CALLING
`PROGRAM
`
`
`
`1.
`144
`
`FIG. 7
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`HPE 1031-0008
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 8 of 10
`
`US 6,247,058 B1
`
`FOREACHENTRY IN
`BROADCAST PACKET
`OUTPUT BUFFER 98, SCAN
`ALL BROADCAST PACKET
`TAGS INALL OUTPUT
`BUFFERS AND COMPARE
`TIME STAMPS TO CLOCK 106
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NO
`
`HAVE ALL
`BROADCAST BUFFER TAGS
`EXCEEDED REACHEDMINIMUM
`TIMEOUT INTERVAL FOR
`ANYBROADCAST
`PACKETS?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`REMOVE FROMALL OUTPUT
`BUFFERS THE BROADCAST
`PACKET TAGS
`CORRESPONDING TO THE
`OLDEST TIMED-OUT
`BROADCAST PACKET
`
`REMOVE OLDEST
`BROADCAST PACKET FROM
`BROADCAST PACKET
`OUTPUT BUFFER 98
`
`176
`
`178
`
`END SUBROUTINE -
`RETURN TO CALLING
`PROGRAM
`
`
`
`
`
`168
`
`18O
`
`FIG. 8
`
`HPE 1031-0009
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 9 of 10
`
`US 6,247,058 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WAIT UNTIL NETWORKSEGMENTS READY TO
`RECEIVE ATRANSMITTED PACKET
`
`184
`SCAN ENTRIES IN OUTPUT BUFFER TO FIND
`OLDEST TIME STAMP
`
`18
`
`SOLDEST
`ENTRY A BROADCAST
`PACKETTAG?
`
`
`
`COMPARE TIME STAMP OF
`PACKET TO CLOCK 106
`
`
`
`90
`1
`
`AS PACKE
`REACHED ACTIVE
`TIMEDOUT
`INTERVAL
`
`ATTEMPT TO TRANSMIT
`PACKET
`
`
`
`DID
`A COLLISION
`OCCURP
`
`195
`
`DD PACKET
`TRANSMIT
`UCCESSFULLY
`
`196
`
`REMOVE PACKET FROM
`OUTPUT BUFFER
`
`198
`
`DISCARD PACKET
`
`200
`
`182
`
`FIG. 9
`
`HPE 1031-0010
`
`

`

`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 10 Of 10
`
`US 6,247,058 B1
`
`COMPARE TIME STAMP OF
`BROADCAST PACKET TO
`CLOCK 106
`
`HAS
`BROADCAST PACKET
`REACHED ACTIVE TIMEOUT
`INTERVAL2
`
`DISCARD
`BROADCAST
`PACKETTAG
`
`NO
`ATTEMPT TO TRANSMIT
`BROADCAST PACKET
`
`
`
`
`
`
`
`DDA
`COLLISION
`OCCURT
`
`216
`
`
`
`
`
`
`
`
`
`206
`
`
`
`
`
`
`
`PACKET TRANSMIT
`SUCCESSFULLY2
`
`
`
`DECREMENT COUNTERVALUE OF
`BROADCAST PACKET IN BROADCAST
`PACKET OUTPUT BUFFER 98 OR
`REMOVE PORT D FROM LIST OF PORT
`IDS
`
`
`
`
`
`
`
`
`
`IS
`OUNTERVALUE ZERO
`OR IS THIS THE LAST
`PORT D?
`
`
`
`210
`
`REMOVE BROADCAST
`PACKET FROM BROADCAST
`PACKET OUTPUT BUFFER 98
`
`214
`
`FIG. 10
`
`HPE 1031-0011
`
`

`

`US 6,247,058 B1
`
`1
`METHOD AND APPARATUS FOR
`PROCESSING NETWORK PACKETS USING
`TIME STAMPS
`
`2
`example, TCP/IP, AppleTalk(R), 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 configured to receive print jobs
`using either the AppleTalkCR 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 verified, 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 verified, 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 verified, 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 (IEEE). 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
`
`FIELD OF THE INVENTION
`The present invention relates to communication between
`network nodes. More Specifically, 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
`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, flow 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 define layers that at least loosely correspond to a
`reference model.
`In the field of computing, there are many popular proto
`cols used to transmit data between network nodes. For
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`HPE 1031-0012
`
`

`

`US 6,247,058 B1
`
`1O
`
`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 amplification 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 amplification 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
`(WAN). 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. A packet
`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
`first 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
`65
`Segment 48 and forwards the packet to that LAN Segment
`where network node 28 receives the packet.
`
`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 define 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 traffic 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 traffic is light.
`Accordingly, many protocols will flood 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 first 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 identified 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
`
`40
`
`45
`
`50
`
`55
`
`60
`
`HPE 1031-0013
`
`

`

`US 6,247,058 B1
`
`S
`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.
`
`15
`
`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 define 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
`first-in first-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 defines 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 specified 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.
`
`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 flowchart illustrating
`how incoming packets are processed by the N port network
`device of FIG. 4.
`FIGS. 7 and 8 are flowcharts illustrating Subroutines that
`remove Stale packets.
`FIGS. 9 and 10, taken together, are a flowchart illustrating
`how outbound packets are processed by the N port network
`device of FIG. 4.
`
`25
`
`35
`
`40
`
`45
`
`50
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`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
`60
`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 configurations are
`possible. For example, in 10-Base-2 Ethernet networks
`
`55
`
`65
`
`HPE 1031-0014
`
`

`

`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 first. 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 timeout interval will be described
`in greater detail below. Note that although the output buffers
`are shown as Separate buffers, those skilled in the art will