`Kalkunte et al.
`
`[54] APPARATUS AND METHOD FOR
`REGULATING ASSIGNED BANDWIDTH IN
`HIGH SPEED PACKET SWITCHED
`NETWORKS
`
`[75] Inventors: M0han V. Kalkunte, Sunnyvale;
`J ayant Kadambi, Milpitas, both of
`Calif.
`
`[73] Assignee: Advanced Micro Devices, Inc.,
`Sunnyvale, Calif.
`
`[21] Appl. No.: 08/884,222
`[22]
`Filed:
`Jun. 27, 1997
`
`[51] Int. Cl.7 ................................................. .. H04L 12/413
`[52] US. Cl. ........................ .. 370/445; 370/447; 370/448;
`370/852; 370/85.6; 340/8255
`[58] Field of Search ................................... .. 370/910, 445,
`370/447, 448, 446, 470, 508, 452, 413;
`340/8255
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6/1994 Fridrich et a1. .
`5,319,641
`5,353,287 10/1994 Kuddes et a1. .
`5,404,353
`4/1995 Ben-Michael et a1. .
`5,418,784
`5/1995 Ramakrishnan et a1. .
`5,422,887
`6/1995 Diepstraten et a1. .
`5,436,903
`7/1995 Yang et a1. .
`5,526,355
`6/1996 Yang et a1. .
`5,642,360
`6/1997 Trainin .
`5,838,688 11/1998 Kadambi et a1. ..................... .. 370/445
`5,854,900 12/1998 K611611116 e161. .
`395/200.68
`5,870,398
`2/1999 Kotchey ................................ .. 370/445
`
`FOREIGN PATENT DOCUMENTS
`
`0632621 A2 1/1995 European Pat. Off. .
`2232855 12/1990 United Kingdom .
`WO92/10041 6/1992 WIPO .
`
`OTHER PUBLICATIONS
`
`US006118787A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,118,787
`Sep. 12, 2000
`
`Preliminary Data Sheet Publication #20550, Rev. B, May
`1996.
`Breyer et al., “Switched and Fast Ethernet: How It Works
`and How to Use It”, Ziff—Davis Press, Emeryville, CA
`(1995), pp. 60—70.
`Johnson, “Fast Ethernet: Dawn of a New Network”, Pren
`tice—Hall, Inc. (1996), pp. 158—175.
`Internet Message to: stds—802—3—hssg.ieee.org, from
`Alakd@aol.com, subject “IPG Issues”, Aug. 27, 1996.
`Internet
`Message
`to:
`Alakd@aol.com,
`stds—802—3—hssg@ieee.org from mart@CS.UCR.edu, sub
`ject “IPG Issues”, Aug. 27, 1996.
`
`(List continued on neXt page.)
`
`Primary Examiner—Michael Horabik
`Assistant Examiner—Prenell Jones
`
`[57]
`
`ABSTRACT
`
`A network interface for a shared gigabit Ethernet network
`selectively modulates an interpacket gap interval following
`a burst transmission in order to establish a rotating priority
`arrangement with network stations on the gigabit network. A
`network station includes a programmable burst timer that
`counts a burst interval corresponding to a negotiated band
`width. The network station having accessed the media
`continues to transmit data packets so long as data is available
`in a transmit buffer, and the burst timer has not expired. Each
`data packet within the burst is transmitted after waiting a
`minimum interpacket gap interval of 96 bit times. Following
`the burst transmission, the network interface waits a modi
`?ed delay interval equal to the minimum interpacket gap
`plus a multiple number of slot times related to the number
`of stations on the network. The modi?ed delay interval is
`decremented by a slot time each time the network station
`detects a burst transmission by another network station.
`Each network station thus transmits a burst of data packets
`according to a negotiated bandwidth, and minimizes the
`number of encountered collisions by deferring to other
`network stations following a burst transmission.
`
`AMD, AM79C971 PCnetTM—FAST Single—Chip Full—Du
`pleX 10/100 mbps Ethernet Controller for PCI Local Bus,
`
`19 Claims, 5 Drawing Sheets
`
`ml
`H (mm
`
`Page 1
`
` Dell Inc.
` Exhibit 1021
`
`
`
`6,118,787
`Page 2
`
`OTHER PUBLICATIONS
`
`Corner, D.E., et al., “A Rate—Based Congestion Avoidance
`and Control Scheme for Packet Switched Networks,” Pro
`ceedings of the International Conference on Distributed
`Computing Systems, Paris, May 28—Jun. 1, 1990, Conf. 10,
`May 28, 1990, IEEE, pp. 390—397.
`Williarnson, C.L. et al., “Loss—IJoad Curves: Support for
`Rate—Based Congestion Control in High—Speed Datagrarn
`Networks,” Proceedings of the Conference on Communica
`tions Architectures and Protocols (SIGCOMM), Zurich,
`
`Sep. 3—6, 1996, vol. 21, No. 4, Sep. 3, 1991, Association for
`Computing Machinery, pp. 17—28.
`
`PouZin, Louis, “Methods, Tools, and Observations on Flow
`Control in Packet—Switched Data Networks,” IEEE Trans.
`on Communications, vol. 29, No. 4, Apr. 1981, New York,
`NY, pp. 413—426.
`
`Gerla, M. et a1., “Congestion Control in Interconnected
`LANS,” IEEE Network, vol. 2, No. 1, Jan. 2, 1988, New
`York, NY, pp. 72—76.
`
`Page 2
`
`
`
`U.S. Patent
`
`Sep. 12,2000
`
`Sheet 1 0f5
`
`6,118,787
`
`3%:3Lu
`
`>-<
`I-
`
`:25
`
`=5:
`
`Eu:
`
`:5
`
`.352.
`
`.3»:55.
`
`3-:
`
`ea
`
`2:.
`
`22.
`
`u..|
`
`XG«
`
`.4
`
`2;.s_2:._:
`
`3<t:;_
`
`>3.
`
`8:
`
`>3.
`
`9.:
`
`=E_<.:]s§
`
`___é=e:
`
`$52.5
`
`=:§:
`
`E2:2$555:
`
`E3:
`
`x.g,w
`
`E2.5:
`
`E2.3:
`
`E2.5:
`
`_o:a_”_
`
`Page 3
`
`Page 3
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 12,2000
`
`Sheet 2 0f5
`
`6,118,787
`
`32....
`
`SE
`
`3.5
`
`SE
`
`32".?
`
`35.53
`
`3:
`
`EM.
`
`3:
`
`S:
`
`$38..
`
`2“33
`
`#33
`
`$33..
`
`:3
`
`._S=zS
`
`5535:
`
`E9.
`
`:32:
`
`5:2
`
`;=$s.§
`
`:2:
`
`3.:
`
`3.5
`
`3.5..
`
`$5”
`
`32::
`
`¥._E._m
`
`E2.5:
`
`Page 4
`
`Page 4
`
`
`
`
`
`U.S. Patent
`
`Sep. 12, 2000
`
`Sheet 3 0f 5
`
`6,118,787
`
`Figure 2A
`
`@1
`
`STORE TB / 62
`H
`I
`RESET BURST TIMER /64
`
`TRANSMIT PI, START BURST TIMER (7°
`
`N0
`
`SUCCESSFUL?
`
`EXTEND TO 4096 BITS/ 32
`
`78
`
`RESET, RESTART
`BURST TIMER
`
`COMPLETE TRANSMISSION, A, 34
`MAINTAIN Tx CARRIER
`
`?]
`RESET BURST‘
`TIMER
`
`Page 5
`
`
`
`U.S. Patent
`
`Sep. 12, 2000
`
`Sheet 4 0f 5
`
`6,118,787
`
`Figure
`
`/92
`SET
`rD= IPG m + (44-1) 45'
`
`Figure 3
`
`HUB
`
`50\
`
`A
`
`44
`
`B
`
`44
`
`42
`.1
`
`50
`
`44
`
`D
`
`44
`
`Page 6
`
`
`
`U.S. Patent
`
`Sep. 12,2000
`
`Sheet 5 0f5
`
`6,118,787
`
`168
`./
`CSMA/CD
`
`MAC
`(ONTROLLER
`1_6__6_
`
`To
`BB/WB DECODER 24
`(Figure I)
`
`160a ___
`
`ts
`
`160b\ .
`
`N
`
`,
`
`T
`
`160 N
`c
`'
`
`‘PG M'"
`
`‘“
`
`1600N
`
`‘BMW
`
`‘___,
`
`1608 \h
`
`Bw
`
`1640
`
`164b\ s
`
`f
`
`D
`
`'___~
`
`164,;\ BURST TIMER
`(t a)
`
`Figure 4
`
`Page 7
`
`
`
`6,118,787
`
`1
`APPARATUS AND METHOD FOR
`REGULATING ASSIGNED BANDWIDTH IN
`HIGH SPEED PACKET SWITCHED
`NETWORKS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to commonly-assigned, appli
`cation Ser. No. 08/622,333, issued US. Pat. No. 5,784,375
`?led Jun. 12, 1996, entitled ROTATING PRIORITY
`ARRANGEMENT IN AN ETHERNET NETWORK, and
`commonly-assigned, copending application Ser. No. 08/706,
`317, ?led Aug. 30, 1996, entitled ARRANGEMENT FOR
`REGULATING PACKET FLOW RATE IN SHARED
`MEDIUM, POINT-TO-POINT AND SWITCHED NET
`WORKS.
`
`10
`
`15
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field
`The present invention relates to a netWork interfacing and
`more particularly, to methods and systems for ef?ciently
`transmitting data packets on a high speed packet sWitched
`netWork, such as a gigabit Ethernet netWork.
`2. Description of the Related Art
`Local area netWorks use a netWork cable or other media
`to link stations on the netWork. Each local area netWork
`architecture uses a media access control (MAC) enabling a
`netWork interface card at each station to share access to the
`media.
`The Ethernet protocol ISO/IEC 8802-3 (ANSI/IEEE Std.
`802.3, 1993 edition) de?nes a half-duplex media access
`mechanism that permits all stations to access the netWork
`channel With equality. Traf?c is not distinguished or priori
`tiZed over the medium. Each station includes an Ethernet
`interface card that uses carrier-sense multiple-access With
`collision detection (CSMA/CD) to listen for traf?c on the
`media. A station having data to send Will attempt to access
`the channel by Waiting a predetermined time after the
`deassertion of a receive carrier on the media, knoWn as the
`interpacket gap (IPG) interval.
`Afull duplex environment has been proposed for Ethernet
`netWorks, referred to as IEEE 802.3x, Full Duplex with
`How Control-Working Draft (0.3). The full duplex environ
`ment provides a tWo-Way, point-to-point communication
`link betWeen tWo netWork stations using a sWitched hub.
`Hence, tWo stations can simultaneously transmit and receive
`Ethernet data packets betWeen each other Without collision.
`The IEEE 802.32 Task Force is currently de?ning stan
`dards for the operation of a shared (i.e., half-duplex) and
`full-duplex gigabit Ethernet. TWo modi?cations have been
`proposed to the existing Ethernet (802.3) protocol for imple
`mentation of shared gigabit Ethernet netWorks, namely
`extending the carrier by increasing the slot time to 512 bytes
`(4096 bits) Without increasing the minimum frame length,
`and providing frame bursting in Which a station sends
`several frames separated by the extend carrier symbols in a
`single burst.
`The proposed frame bursting for gigabit Ethernet operates
`by a station operating according to the conventional CSMA/
`CD protocol When attempting to transmit the ?rst packet. A
`burst timer is started at the beginning of the transmission of
`the ?rst frame. If the ?rst packet transmission is successful,
`the station can send an additional frame provided the fol
`loWing tWo conditions hold: (1) the burst timer has not
`expired, and (2) the station has another frame to send. This
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`step is repeated until the burst timer expires or the station has
`no frame to send, Whichever occurs ?rst. The carrier sense
`is held high by the transmitting station during the entire
`burst. The IEEE 802.32 Task Force is currently contemplat
`ing setting the burst timer to limit the burst duration to a
`maximum duration of 65536 bits.
`If a collision occurs during transmission of the ?rst frame
`on the gigabit Ethernet media, the station folloWs the normal
`CSMA/CD operation sequence of jam, abort, and backoff
`collision mediation. A neW burst of frames can occur only
`When a station has sent the ?rst packet successfully.
`Prior efforts at rate control of a shared medium typically
`involved use of a central management entity. For example,
`a token ring netWork passes a token in a sequential manner
`to netWork stations. Astation that acquires the token has the
`right to transmit on the netWork. Upon completion of the
`transmission, the token is passed on to the next station. The
`passing of the token, hoWever, uses up bandWidth on the
`media. BandWidth is also Wasted if the token is received and
`then passed by a station that has no data to transmit. Hence,
`the token ring netWork limits netWork throughput because an
`individual station cannot transmit data until it receives the
`token, regardless of Whether any other station has any data
`to send.
`Another netWork arrangement speci?ed by IEEE 802.12
`1995, “Demand Priority Access Method, Physical Layer and
`Repeater Speci?cation for 100Mb/s Operation,” also knoWn
`as the VG ANY LAN netWork, uses a centraliZed hub to
`arbitrate among the requests from netWork stations. The hub
`grants access to the stations in a round robin fashion.
`HoWever, the VG ANY LAN netWork still requires control
`by a central hub.
`Other proposals suggest the user of a central management
`entity to assign a slot number to each station on the netWork,
`Where a station transmits only When a current slot number is
`equal to the station slot number. Such proposals also require
`a centraliZed management entity to manage the netWork.
`
`DISCLOSURE OF THE INVENTION
`
`There is a need for an arrangement for accessing media of
`a gigabit Ethernet netWork, Where stations establish a rotat
`ing priority arrangement for transmitting a burst of data
`packets Without the use of a centraliZed management entity.
`There is also a need for an arrangement in a netWork
`station that transmits data packets on a high speed packet
`sWitched netWork according to a desired transmission rate
`Without the necessity of external monitoring or control.
`These and other needs are attained by the present
`invention, Where the interpacket gap interval folloWing a
`burst transmission of selected duration is modulated based
`on the number of stations to enable a rotating priority
`arrangement betWeen the stations on the high speed packet
`sWitched netWork.
`According to one aspect of the present invention, a
`method in a netWork station for transmitting data packets
`onto netWork media includes setting a burst timer to a burst
`interval, transmitting a ?rst data packet onto the netWork
`media, starting the burst timer in response to the ?rst data
`packet transmitting step, transmitting a second available
`data packet folloWing the ?rst data packet transmitting step
`after a predetermined interpacket gap interval and based on
`the burst timer having a value Within the burst interval,
`Waiting a delay time, including the predetermined inter
`packet gap interval and an integer multiple of a predeter
`mined delay time interval, before accessing the media based
`on the burst timer having passed the burst interval, Wherein
`
`Page 8
`
`
`
`6,118,787
`
`3
`the integer is related to a number of stations connected to the
`network media and the predetermined delay time interval is
`related to a predetermined slot time. Waiting the delay time
`having the integer multiple of predetermined delay time
`intervals after a burst interval ensures that a netWork station
`having transmitted a burst of data packets defers to other
`stations attempting transmission, minimiZing the number of
`collisions on the media. Moreover, setting the integer mul
`tiple of delay time intervals based on the number of stations
`connected to the netWork media and setting the predeter
`mined delay time interval relative to the predetermined slot
`time ensures that the netWork stations can operate according
`to a rotating priority arrangement, Where each station has a
`corresponding deferral interval that is consistent With the
`propagation characteristics of the high speed packet
`sWitched netWork.
`Another aspect of the present invention provides a net
`Work interface for connection With netWork media. The
`netWork interface includes a carrier sensor con?gured for
`sensing a carrier on the media, a ?rst programmable timer
`con?gured for counting a programmed burst interval, a ?rst
`programmable delay timer con?gured for counting at least
`one of a minimum interpacket gap interval and a pro
`grammed delay interval, a controller, and a transmitter. The
`controller is con?gured for setting the ?rst programmable
`delay timer With one of the minimum interpacket gap
`interval and the programmed delay interval, setting the
`programmed delay interval to a maximum value of the
`minimum interpacket gap interval plus a prescribed integer
`multiple of slot times, Where the prescribed integer is related
`to the number of stations on the netWork, and decreasing the
`programmed delay interval in the ?rst programmable delay
`timer by a slot time in response to detection of the carrier
`during transmission of a burst of data packets by another
`netWork station. The transmitter is con?gured for outputting
`a burst of data packets onto the media during the pro
`grammed burst interval, and Waiting the minimum inter
`packet gap interval during the programmed burst interval
`and at least the programmed delay interval after the pro
`grammed burst interval. The controller controls the pro
`grammable delay timer to provide a minimum interpacket
`gap interval during burst transmissions and a programmed
`delay interval after the burst transmission, Where the pro
`grammed delay interval is set by the controller to enable
`other netWork stations to access the media folloWing the
`burst transmission. Moreover, the controller enables the
`netWork interface to operate according to a rotating priority
`arrangement With other netWork stations by decreasing the
`programmed delay interval by a slot time in response to
`detection of the carrier during transmission of a burst of data
`packets by another netWork station. Hence, the controller
`maintains the position of the netWork interface relative to
`other netWork stations by changing the programmed delay
`interval based on transmissions by the netWork interface and
`by other netWork stations. Use of the ?rst programmable
`timer for counting a programmed burst interval also enables
`the netWork interface to transmit a burst of data packets
`during a programmed burst interval according to a negoti
`ated bandWidth, Where different netWork stations transmit at
`different burst intervals based on respective assigned band
`Width allocations.
`Additional objects, advantages and novel features of the
`invention Will be set forth in part in the description Which
`folloWs, and in part Will become apparent to those skilled in
`the art upon examination of the folloWing or may be learned
`by practice of the invention. The objects and advantages of
`the invention may be realiZed and attained by means of the
`
`4
`instrumentalities and combinations particularly pointed out
`in the appended claims.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`Reference is made to the attached draWings, Wherein
`elements having the same reference numeral designations
`represent like elements throughout and Wherein:
`FIGS. 1, 1A and 1B are block diagrams of a netWork
`interface according to an embodiment of the present inven
`tion.
`FIGS. 2A and 2B are How diagrams summariZing a
`method in a netWork station of transmitting data packets
`according to an embodiment of the present invention.
`FIG. 3 is a diagram illustrating a gigabit netWork.
`FIG. 4 is a block diagram of the media access control
`(MAC) of FIG. 1.
`
`BEST MODE FOR CARRYING OUT THE
`INVENTION
`
`FIG. 1 is a block diagram of an exemplary netWork
`interface 10 that accesses the media of a gigabit Ethernet
`(ANSI/IEEE 802.32) netWork according to an embodiment
`of the present invention.
`The netWork interface 10, preferably a single-chip, 32-bit
`Ethernet controller, provides an interface betWeen a local
`bus 12 of a computer, for example, a peripheral component
`interconnect (PCI) local bus, and an Ethernet-based gigabit
`media 50. An exemplary netWork interface is the Am79C971
`PCnetTM-FAST Single-Chip Full-Duplex Ethernet Control
`ler for PCI Local Bus, disclosed in Preliminary Data Sheet
`Publication #20550, Rev. B, Issue Date May, 1996, from
`Advanced Micro Devices, Inc., Sunnyvale, Calif. According
`to the disclosed embodiment, the AM79C971 Would be
`modi?ed to send and receive data packets on the netWork
`media 50 at gigabit rate across a physical layer device (e.g.,
`a gigabit serial transceiver).
`The interface 10 includes a PCI bus interface unit 16, a
`direct memory access (DMA) buffer management unit 18,
`and a netWork interface portion 20. The netWork interface
`portion 20 includes a media access control (MAC) core 22,
`a Gigabit Media Independent Interface (GMII) 23b for
`connecting external 10Mb/s, 100Mb/s or 1000Mb/s
`transceivers, an External Address Detection Interface
`(EADI) 23c, and an 8B/10B decoder 24. The interface 10
`also includes an EEPROM interface 28, an LED control 29,
`and an expansion bus interface 31 for boot RAM (e.g.,
`EPROM or Flash memory) during startup, and an IEEE
`1149.1-compliant JTAG Boundary Scan test access port
`interface 36. Full-duplex operation can be performed by the
`MII interface. Additional details of these interfaces are
`disclosed in the above-referenced Am79C971 Preliminary
`Data Sheet.
`Although the above-described interfaces provide user
`?exibility, the interfaces can be reduced to the Gigabit
`Media Independent Interface 23b for gigabit transmissions.
`The netWork station 10 also includes a PCI bus receive
`?rst in ?rst out (FIFO) buffer 30a, a MAC receive FIFO
`buffer 30b, a PCI bus transmit FIFO buffer 32a, a MAC
`transmit FIFO buffer 32b, and a FIFO controller 34.
`The PCI bus interface unit 16, compliant With the PCI
`local bus speci?cation (revision 2.1), receives data frames
`from a host computer via the PCI bus 12. The PCI bus
`interface unit 16, under the control of the DMA buffer
`management unit 18, receives transfers from the host com
`puter via the PCI bus 12. The data received from the PCI bus
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 9
`
`
`
`6,118,787
`
`10
`
`15
`
`20
`
`5
`interface unit 16 are passed to the PCI bus transmit FIFO
`buffer 32a, and subsequently to the MAC transmit FIFO
`buffer 32b.
`The buffer management unit 18 manages the reception of
`the data by the PCI bus interface unit 16 and retrieves
`information from header bytes that are transmitted at the
`beginning of transmissions via the PCI bus 12. The header
`information identifying the byte length of the received frame
`is passed to the FIFO control 34.
`The netWork interface 10 includes a netWork port man
`ager 38, and an auto-negotiation unit 40. The auto
`negotiation unit 40 communicates via the media 50 With a
`corresponding auto-negotiation unit in the hub serving the
`netWork interface 10, described beloW, With a corresponding
`auto-negotiation unit in a centraliZed hub, repeater, or sWitch
`that provides shared receive carrier and collision signals
`betWeen different netWork stations.
`As described in detail beloW, the above-described MAC
`22 is con?gured to operate in a shared gigabit Ethernet
`netWork by providing a burst of data packets according to a
`burst timer, shoWn in FIG. 3. As described beloW, the
`disclosed MAC 22 transmits a burst of data packets accord
`ing to a rotating priority arrangement, Where the interburst
`gap (i.e., the delay interval folloWing deassertion of a carrier
`sense) is modulated in each netWork station to establish a
`rotating priority arrangement betWeen the respective net
`Work stations. When a station is alloWed to transmit, the
`netWork station transmits according to a programmed burst
`timer length, Where the programmed burst interval is gen
`erated by an external management entity based on the
`assigned transmission rate of the corresponding netWork
`station. Hence, the disclosed arrangement enables different
`netWork stations to transmit according to different assigned
`transmission rates, While at the same time minimiZing the
`number of collisions by establishing a rotating priority
`arrangement, Where each station selectively modulates the
`interburst delay time based on the number of stations on the
`netWork.
`FIGS. 2A and 2B are How diagrams summariZing the
`method of accessing the media according to an embodiment
`of the present invention. The method begins in step 60,
`Where the MAC 22 stores in a register the number of stations
`(N) connected to the netWork media 50. The number of
`stations (N) may be supplied by an external management
`entity, for example an auto-negotiation unit Within a netWork
`hub or repeater, or by a user such as a netWork designer.
`Alternatively, the number of stations (N) may be indepen
`dently determined by the netWork station based on collisions
`detected on the media.
`The MAC 22 then receives and stores in step 62 a burst
`interval (tB) that speci?es the maximum duration of a burst
`of data packets by the netWork station. Although the burst
`interval (tB) may be set to a prescribed value, for example
`12000 bits or 64 kilobits (as proposed by the IEEE 802.32
`Task Force), a particular feature of the present invention is
`that the burst timer interval be con?gured based on a
`prescribed minimum burst interval (tBMIN) and an allocated
`bandWidth (BW), Where tB=tBM,N><BW. Hence, the burst
`time interval can be speci?ed by an external management
`entity by supplying the bandWidth multiplier (BW) to each
`corresponding netWork station.
`As an example of setting the burst interval based on the
`prescribed minimum burst interval and the assigned band
`Width allocation (BW), consider an exemplary netWork
`having four netWork stations, A, B, C, and D, shoWn in FIG.
`3. The hub 42 Will knoW the number of stations 44 on the
`
`6
`netWork, and Will transmit the number of stations on the
`netWork (N), and an allocated bandWidth
`Assuming
`each station 44 is required to share the bandWidth equally,
`the burst timer length Will be equal in each corresponding
`station 44, for example tBA=tBB=tBC=tBD,=tBMIN. As
`described above, the value for tBMIN may be set at 12000 bits
`or 64 kilobits, as desired. HoWever, the maximum value
`tB= BMINXBW should be no greater than 65536, if IEEE
`compliance is preferred. The minimum burst timer length
`must be at least 12000 bits since the maximum frame length
`is 1518 bytes (12144 bits). If each station 44 has the same
`burst timer length, then each station on average gets 25%
`bandWidth.
`Assume noW that an external management entity decides
`that station A needs 40% bandWidth, and that the remaining
`stations B, C, and D share the remaining bandWidth equally.
`In such a case, the ratio of burst length timers are 2:1:1:1,
`Where stations B, C, and D get 20% of the usable bandWidth,
`respectively. In such a case, the hub 42 Would output a
`bandWidth allocation multiplier of BW=2 to station A, and
`a multiplier of BW=1 to stations B, C, and D. Hence,
`different bandWidths for different stations can be maintained
`by having different ratios (BW) and setting the burst timer
`length based on the prescribed minimum burst interval and
`the assigned bandWidth allocation.
`Referring to FIG. 2A, once the burst interval (tB) is set in
`step 62, the MAC 22 resets the burst timer in step 64. The
`MAC 22 then begins transmission mode in step 66 by
`Waiting the minimum interpacket gap interval (IPGMIN) of
`96 bit times in step 66. While Waiting the minimum inter
`packet gap interval, the MAC 22 checks in step 68 Whether
`a carrier is sensed in step 68 according to CSMA/CD
`protocol. If a carrier is sensed in step 68, the MAC 22
`continues to defer to the transmission on the media.
`HoWever, if in step 68 the MAC 22 does not detect a carrier
`sense signal (CRS) from the physical layer (not shoWn)
`during the delay interval IPGMIN, the MAC 22 in step 70
`begins to transmit a data packet (P1) and concurrently starts
`the burst timer after Waiting the delay interval IPGMIN. Once
`the MAC 22 begins transmitting the data packet (P1), the
`MAC 22 checks in step 72 Whether a collision is encoun
`tered. If a collision is detected by the MAC 22 in step 72, the
`MAC 22 performs collision mediation according to the
`truncated binary exponential backoff (TBEB) algorithm in
`step 74. If the MAC 22 is successful during the collision
`mediation of step 74 in transmitting a data packet on the
`media in step 76, the MAC 22 resets and restarts the burst
`timer in step 78 based on the successful access of the media
`by the netWork station. HoWever, if in step 76 the MAC 22
`determines that collision mediation Was unsuccessful, Where
`another netWork station has gained access to the media, then
`the MAC 22 returns to step 64 to reset the burst timer and
`defer to the station currently transmitting on the media. As
`recogniZed in the art, the collision mediation of step 74 may
`involve repeated collisions betWeen contending netWork
`stations before one netWork station successfully transmits a
`data packet on the medium.
`Assuming the netWork station has gained access to the
`medium 50 during transmission of the ?rst data packet (P1),
`the MAC 22 checks in step 80 Whether the transmitted data
`packet (P1) is less than 4096 bits, i.e., Whether the trans
`mitted data packet is less than a single slot time. If the ?rst
`transmitted data packet (P1) is less than 4096 bits, the MAC
`22 outputs extension bits after the ?rst transmitted data
`packet (P1) in step 82 to provide a total of 4096 bits
`transmitted by the MAC 22 as a single frame. The MAC 22
`then completes transmission of the ?rst data packet (P1) in
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 10
`
`
`
`6,118,787
`
`7
`step 84, and maintains the carrier on the media for example
`by continuing to assert the TXiEN signal by the MII port
`23b. Speci?cally, the MAC 22 continues to assert the carrier
`signal if another data packet is to be transmitted as part of
`a burst transmission. Accordingly, the MAC 22 checks in
`step 86 if the transmit FIFO 32b has additional transmit data
`for transmission on the medium. If the transmit FIFO 32 has
`more transmit data to be transmitted, MAC 22 checks in step
`88 Whether the burst timer has expired after Waiting the
`minimum IPG in step 87. If the burst timer has not expired,
`the MAC 22 starts transmission of the next data packet in
`step 90. Hence, the MAC 22 continues to assert the carrier
`signal so long a (1) the transmit FIFO 32 has another data
`packet to send, and (2) the burst timer has not expired.
`
`5
`
`8
`netWork station transmitting a burst of data packets Will
`continue to assert the carrier sense until completion of the
`burst. Upon sensing deassertion of the receive carrier, the
`MAC 22 decreases the programmed delay interval (tD) by a
`slot time (t5) in step 100, and Waits the programmed delay
`interval in step 94 before attempting access of the medium.
`
`Use of the above-described programmed delay interval
`(tD) as the interpacket gap interval folloWing a burst trans
`mission establishes a rotating priority mechanism betWeen
`netWork stations, Where a station having a deferral interval
`tD=IPGMIN gains access by having the highest priority to the
`media. Table 1 illustrates the sequence of slot times added to
`the delay interval (tD) in the
`
`TABLE 1
`
`STATION
`
`SEQUENCE 1
`
`SEQUENCE 2
`
`SEQUENCE 3
`
`SEQUENCE 4
`
`SEQUENCE 5
`
`A
`B
`c
`D
`
`0
`1
`2
`3
`
`3
`0
`1
`2
`
`2
`3
`0
`1
`
`1
`2
`3
`0
`
`0
`1
`2
`3
`
`As described above, the MAC 22 continues to transmit a
`burst of data packets so long as transmit data is available in
`the transmit FIFO 32, and so long as the burst timer has not
`expired. As described above, the burst timer may be set to a
`selected value based on the corresponding bandWidth
`assigned to the netWork station. The MAC 22 can thus
`continue to transmit a burst of data packets until the burst
`timer expires. Once the MAC 22 determines in step 88 that
`the burst timer has expired, or if the transmit FIFO 32 runs
`out of data, the MAC 22 terminates the burst transmission by
`deasserting the carrier, resetting the burst timer in step 91,
`and Waiting an interburst delay interval as illustrated in FIG.
`2B.
`As shoWn in FIG. 2B, the MAC 22 sets the interburst
`delay interval (tD) equal to a maximum value of the mini
`mum interpacket gap interval (IPGMIN) plus an integer
`multiple of slot times related to the number of stations on the
`netWork in step 92. Speci?cally, once the MAC 22 has
`completed a transmission of a burst of data packets accord
`ing to steps 86 and 88, the MAC 22 sets the delay interval
`(tD) to the maximum value of tD=IPGM,N+(N—1)tS in step 92,
`Where N equals the number of stations on the netWork. The
`MAC 22 then Waits the programmed interburst delay inter
`val (tD) in step 94 folloWing deassertion of the receive data
`valid carrier.
`Hence, the MAC 22 Waits a maximum delay interval of
`the minimum interpacket gap plus (N-1) slot times after
`transmitting a burst of data packets. While Waiting this
`extended interpacket gap interval at the end of the burst, at
`least one netWork station having data to transmit Will Wait
`the minimum IPG of 96 bit times before accessing the
`media. Hence, if the MAC 22 senses a carrier in step 96
`asserted by another netWork station, the MAC 22 Will defer
`to the transmitting netWork station in step 98. Assuming the
`netWork is idle and the MAC 22 does not sense a carrier
`While Waiting the delay interval tD, the MAC 22 returns to
`step 70 to begin transmission of another burst starting With
`a data packet (P1).
`Hence, the MAC 22 defers to other netWork stations
`transmitting a burst of data packets in step 98. The MAC 22
`Will monitor the netWork media in step 98 to determine When
`the carrier sense (CRS) is deasserted. As described above, a
`
`25
`
`30
`
`35
`
`45
`
`55
`
`65
`
`As shoWn in Table 1, sequence 1 corresponds to an
`example Where stations A, B, C, and D have delay values
`tDA=IPGM,N, tDB=IPGM,N+tS, tDC=IPGM,N+2tS, and tDD=
`IPGM,N+3tS. Note the IPGMIN values are omitted for sim
`plicity from Table 1. Assuming station A has transmitted a
`burst of data packets, the delay values tD are reduced in
`stations B, C, and D, and the delay value of station A (tDA)
`is reset to obtain the delay sequence shoWn in sequence 2,
`Where station B has the shortest delay time. Assuming
`station B has transmitted a burst of data packets in sequence
`2, each station Will change the corresponding delay interval
`tD to produce sequence 3, Where station C has the minimum
`delay time. The same rotating priority arrangement Will
`apply for sequences 4 and 5.
`Hence, the arrangement of the present invention assures