Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
1999-02-26
2004-02-24
Ton, Dang (Department: 2666)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C370S472000, C709S223000
Reexamination Certificate
active
06697383
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to a method and system for remotely awake the sleeping nodes on the communications network, and in particular, to a method and system for detecting specific type of data in the stream on the local area network (LAN).
2. Description of the Related Art
An Ethernet network which meets ANSI/IEEE 802.3 is usually used in a local area network, in which multiple computer nodes are connected to a single shared serial data path. Typically, only one node can transmit data onto the path at a time. A node connected to the path transmits data in the form of a packet that includes a destination address. The packet transmits through the network medium and is received by all other nodes. The addressed node duplicates the entire packet as it goes by; the others rejects the packet after determining that it is addressed to another node.
A Media Access controller (MAC) serves as an interface between a shared data path and the computer node connected to that path. Each node connected to the network includes a MAC that performs a number of functions involved in the transmission and reception of data packets. Further details on the Ethernet networks including the MAC is provided by Crayford, Advanced Micro Devices, U.S. application Ser. No. 07/841,113, filed on Feb. 24, 1992 and entitled, “Ethernet Media Access Controller with External Address Detection Interface and Associated Method,” now U.S. Pat. No. 5,305,321, the disclosure of which is incorporated herein by reference.
ROC patent Pub. No. 225,073 (The corresponding U.S. Pat. No. is 5,404,544.), entitled “AUTO-WAKE FOR ETHERNET 10 BASED-T CONTROLLER,” filed by Advanced Micro Devices (AMD) on Dec. 3, 1992 discloses such a system and method for automatic connection and disconnection of a node on a LAN by way of the power management of the LAN controller. Further, AMD also discloses a so-called Magic Packet technique for remotely waking up the sleeping computer host on a network. It is implemented by sending a specific information packet, Magic Packet, to a node on the computer network such that when a computer capable of receiving the specific packet goes to sleep, it enables the Magic Packet mode in the LAN controller, and the computer host
10
will alert the system to wake up while the LAN controller
15
receives a Magic Packet frame. The Magic Packet frame certainly meets the fundamental requirements of any one of the selected LAN techniques such as Ethernet and Token Ring, for example, SOURCE ADDRESS, DESTINATION ADDRESS (which may be an IEEE address of the receiving node or a MULTICAST address including BROADCAST address), and CRC(Cyclic Redundancy Check). The Magic Packet consists of sixteen duplications of consecutive specific sequence of the node's IEEE address of six bytes, without interruptions or breaks, wherein the specific sequence may be preceded by a synchronous stream and located anywhere within the Magic Packet. The synchronous stream is so designed that scanning state machine for the input status of the LAN controller
15
may be constructed much simpler. The synchronous stream is defined as a sequence of hexadecimal FFh having six bytes length.
In view of the above, the matching technique is actually a string searching technique. Since the network frame is a string of bytes, the Magic Packet matching is to search a specifically predefined data sequence within a string. A conventional string searching such as the book, entitled“Algorithm in C,” 1990 Addison-Wisely, by Robert Sedgewick, which introduces a so-called Brute-Force and Kauth-Morris-Pratt (KMP) algorithm and Boyer-Moorse (BM) algorithm. The applicants, however, found that when applying to the Magic Packet matching, the above algorithms can not meet the requirements of detection time, size of memory, implementation complexity and difficulties in set-up.
In Brute-Force algorithm, the detecting process goes back while failing to search the target, which does not effectively utilize the information of the comparison history. Thus, the Brute-Force algorithm inevitably repeats its comparison process, fails to operate in real time and also needs to store the received bytes as an indication of the back-off search. According to the characteristics of the pattern to be compared, the KMP or BM algorithms both employ the properties of the comparison results. Further, prior to searching the string, these algorithms will set up in a real-time manner a look-up table in which the location of the byte to be compared while the current comparison fails indicated, thus inevitably increase the complexity thereof. To the contrary, the subject invention simplifies the searching algorithm according to the characteristics of the Magic Packet Pattern and dynamically constructs the registers for registering the back-off comparison condition, thus reduce the implementation complexity.
The comparison of the claimed algorithm of the present invention and the above-mentioned algorithms are tabulated for reference as follows:
TABLE 1
The Present
Brute-Force
KMP or BM
Invention
Time
Long.
Short.
Short.
Consuming
The back-off
Forward
Forward
comparison is needed
comparison
comparison need
when the comparison
need not to
not to go back for
fails.
go back for
comparison.
If packet length is N,
comparison.
The most
and length of the
The most
comparing times
pattern to be
comparing
are N.
compared is M, the
times are
most comparing times
M + N.
are M*N.
Storage
A large amount
A small
A small amount of
Memory
thereof is needed.
amount
memory id needed.
needed
All the packet must be
thereof is
The compared
stored so as to effect
needed. The
bytes need not to
the back-off
compared
be stored.
comparison when the
bytes need
current comparison
not to be
fails
stored.
Implemen-
Simple.
Complex'it
Simple, which can
tation
It may be
needs a
be implemented by
Complexity
implemented by some
micro-
means of basic
of counters,
program to
logical elements.
comparators, and so
control the
on.
comparison
process
Difficulty
Simple.
Complex.
Simple.
of Set-up
It only needs to set
It must set
Only to set the
the pattern to be
up the next
pattern (node
compared.
table when
address) to be
the current
compared is
comparison
needed,
fails.
SUMMARY OF THE INVENTION
To avoid the above-mentioned problems encountered in the prior art, the present invention discloses an effectively operative method and system that utilizes only two sets of counter logics and the associated control logics to detect, in real time, the Magic Packet without utilizing a large amount of memory or complex algorithm.
According to the Magic Packet detecting system of the present invention, when a LAN controller of a node on the network receives the data streams addressed in the node, the detecting system of the present invention in which a Sync Counter and a Pattern Counter operates individually, starts to compare, on the byte basis, the input bytes within the streams and to determine whether or not any one of which matches the expected Magic Packet bytes. The Sync Counter continues to increase its count value as the received byte is a synchronous byte FFh until the count value equals to the number of the consecutive synchronous bytes preceding the Magic Packet pattern. (The count value need not equal to the byte length of synchronous bytes, since the physical address of a node probably includes synchronous bytes as well.) The Sync Counter clears the count value if the received byte is not a synchronous byte such that the number of the consecutive synchronous bytes may be counted. The Pattern Counter increases its count value as the input byte matches the Magic Packet bytes to be compared such that the exactly compared bytes are counted. If each of the input bytes does not match the expected byte and is a synchronous byte, meaning that the data streams including the received bytes encompass a consecutive sequence, the number of the consecutive synchronous bytes registered in the Sync Counter is loaded into the Pattern Counter for further computation of the
Li Yuan-Hwa
Lu Mei-Chuan
Wey Yih-Sheng
Merchant & Gould P.C.
Ton Dang
Tran Phuc
LandOfFree
Method and apparatus for detecting data streams with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting data streams with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting data streams with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289900