Electrical computers and digital processing systems: multicomput – Miscellaneous
Reexamination Certificate
2000-03-08
2003-07-29
Barot, Bharat (Department: 2154)
Electrical computers and digital processing systems: multicomput
Miscellaneous
C709S228000, C709S234000, C709S235000, C709S250000, C370S347000, C370S348000
Reexamination Certificate
active
06601085
ABSTRACT:
FIELD OF INVENTION
The present invention relates to network communications, and more particularly, to multi-MAC chips used for an Ethernet network.
BACKGROUND
A portion of an Ethernet LAN (Local Area Network) is illustrated in FIG.
1
. Switch
102
is a four-port switch, with ports connected to DTE (Data Terminal Equipment)
104
, Hub
106
, Hub
108
, and three-port switch
110
. Connected to Hub
106
are DTE
112
, DTE
114
, and DTE
116
, and connected to Hub
108
are DTE
118
and DTE
120
. Data terminal equipment may be, for example, a workstation or server. A hub may be a half-duplex or full-duplex repeater. The connections to switch
110
are not shown for simplicity, but may be connected to other switches, hubs, DTE, or other intermediate network devices.
FIG. 2
illustrates a model of a switch. For simplicity, only two ports are indicated, where PHY (Physical Layer)
202
and PHY
204
are connected, respectively, to links
206
and
208
. The conceptual layers immediately above PHY
202
and PHY
204
, respectively, are MAC (Media Access Control)
210
and MAC
212
. Switch control layer
214
communicates with the MAC layers and routes received MAC frames to their appropriate MAC layers for transmission on the appropriate port. See IEEE (Institute of Electrical and Electronic Engineers) standard 802.3 for definitions of the various protocol layers.
For an Ethernet, when a collision is detected by a MAC while transmitting a frame, it interrupts transmission of the frame and causes a JAM signal to be transmitted so that all other MACs on the shared medium are notified that a collision has occurred. The MAC will retry transmission of the interrupted frame until transmission is successful or a maximum number of attempts (attemptLimit) have been made. All attempts at. transmitting an interrupted frame are made before transmitting any subsequent outgoing frame.
Retransmission of an interrupted frame is scheduled by a random process known as a truncated binary exponential backoff. The MAC enters a delay period after it has sent the last jam bit, where the delay is an integral multiple of slotTime. The number of slotTimes in the delay before the n
th
retransmission attempt is the random variable r, where r is an integer-valued-random variable uniformly distributed within the range
0≦
r<
2
k
,
where
k=
min(
n,
10).
A method for generating realizations of the random variable r is illustrated in FIG.
3
. Ring oscillator
302
provides a clock signal to free-running counter
304
. Ring oscillator
302
is designed so that its frequency, and hence the clock signal used to clock counter
304
, is a function of temperature or other environmental factors. Counter
304
is sampled and latched by latch
306
when a collision is detected. Any chosen k bits of latch
306
provide a realization of the random variable r.
Some switches use multi-MAC chips, in which two or more MACs are integrated on the same die. Furthermore, some hubs may also employ multiple MAC layers integrated on the same die, such as full-duplex hubs. It may happen, perhaps inadvertently, that two or more MACs on the same multi-MAC chip are connected to the same network segment. Or perhaps there is a path connecting one MAC on a multi-MAC chip to another MAC on the same multi-MAC chip. In such a situation, one MAC on a multi-MAC chip may cause a transmission collision with another MAC on the same multi-MAC chip.
For prior art multi-chip MACs utilizing one oscillator, the random variables generated for each MAC will be the same. For multi-chip MACs utilizing more than one oscillator, each oscillator experiences essentially the same environmental factors, and consequently the random variables generated by each MAC will be correlated. In the worst case, the randomly generated integers will be the same. Correlated random variables among colliding MACs reduce the effectiveness of the truncated binary exponential backoff algorithm. In particular, when the generated random variables are the same, colliding MACs will enter a live-lock situation when they cause collision, because each colliding MAC will retry transmission at the same time, until attemptLimit is reached, in which case an error indication is provided to a higher layer. There is thus a need to address the problem of live-lock in a multi-MAC chip.
REFERENCES:
patent: 5822538 (1998-10-01), Krishna et al.
patent: 5854900 (1998-12-01), Kalkunte et al.
patent: 5894559 (1999-04-01), Krishna et al.
patent: 5905870 (1999-05-01), Mangin et al.
patent: 6055578 (2000-04-01), Williams et al.
patent: 6078591 (2000-06-01), Kalkunte et al.
patent: 6339788 (2002-01-01), Geyer et al.
patent: 6345310 (2002-02-01), Allison et al.
Ende Benzi
Wertheimer Aviad J.
Barot Bharat
Kalson Seth Z.
LandOfFree
Collision live lock avoidance for multi-mac chips does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Collision live lock avoidance for multi-mac chips, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collision live lock avoidance for multi-mac chips will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3038503