Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
1998-09-29
2003-02-18
Ngo, Ricky (Department: 2664)
Multiplex communications
Pathfinding or routing
Store and forward
C370S235000, C370S401000, C370S463000
Reexamination Certificate
active
06522656
ABSTRACT:
BACKGROUND OF THE INVENTION
Ethernet switch architecture can be generally divided into two classes: shared memory and multiprocessor systems. In the shared memory architecture, packets, including a header with a source and destination addresses, a data payload, and a check sum portion at the end of the packet, are received at the ports and then forwarded to a system card via a backplane. Here, the packets are buffered in the same central memory, which is accessed by a single central controller. This controller looks at the destination address of the packet, and possibly other information such as source port and destination port, and then, via an address and other look-up tables, determines what should be done with the packet, such as forward, discard, translate or multicast. This forwarding decision is usually an identification of a LAN Card and a port of that LAN Card in the Ethernet switch that connects to the destination address. The address look-up table tells to which port of the Ethernet switch the packet must be sent to reach the addressed device. The packet is then forwarded to that LAN card. The designated LAN card receives the packet and routes it to the destination port where an Ethernet controller chip sends the packet out on the LAN to the addressed device.
The multiprocessing architecture differs in that a local processor is placed on each one of the cards and each one of these processors accesses and maintains its own address table. As a result, when a multiprocessor-type LAN card receives a packet through one of its ports, it first looks at the destination address and then determines to which one of the other ports on one of the other cards it must be sent and then sends the packet to that card via the backplane connecting the cards. If the port address of the packet happens to be on the same LAN card it was received on, the processor simply sends the packet to that local port address and the packet is never transferred on the backplane. This architecture has certain advantages in that since functionality is replicated between the cards, if any one of the cards should fail the Ethernet switch can still function although this also increases cost. One problem is, however, that a substantial amount of processing and software is devoted to ensuring the address tables on each one of the LAN cards are exact duplicates of each other.
Regarding the handling of the packet within the Ethernet switch, two basic methods are conventional. The first is called store and forward switching. In this switching scheme, a particular LAN card will wait until it has received the entire packet before forwarding it to either another LAN card or the central controller card. This allows the LAN card to confirm the packet is valid and uncorrupted by reference to the check sum information contained at the end of the packet. A new approach has been proposed which is called cut-through switching, a purpose of which is to decrease packet latency. Here, not yet fully received packets are forwarded to the destination port and begun to be sent out or broadcasted from the switch before the entire packet has been received. This both decreases packet latency and also decreases the amount of buffering RAM required by each LAN card. The problem with this approach, however, is that if the packet turns out to be invalid or corrupted there is no way to drop the packet since it is already been started to its destination.
SUMMARY OF THE INVENTION
The present invention is directed to a distributed processing archecture which yields most of the simplicity of the shared memory configuration while attaining the advantages and faster operation of multiprocessing configuration. In general, this is achieved by a packet switching system that includes at least two network cards each receiving data packets via a plurality of associated ports, a system card, and an interconnect for connecting the system card to the network cards. Each one of the network cards comprises a plurality of port controllers for sending and receiving packets to and from a corresponding port and a packet processor for buffering packets received by the port controllers. The packet processor then sends destination addresses to the system card via the interconnect and receives forwarding information from the system card. The processor then forwards the packet in response to the forwarding information.
In specific embodiments, the system card comprises an address look-up table correlating destination addresses with the ports of the system. Also, the packet is forwarded to a different one of the network cards indicated by the forwarding information via the interconnect.
The packet processor can be a hardware processor or even a programmable gate array.
In yet another embodiment, the processor begins forwarding the packet in response to the forwarding information before the packet has been entirely received and checks the validity of the packet by reference to check sum information contained in the packet. Future packets from the source port have their validity checked prior to forwarding in response to receiving an invalid packet from the source port.
In general, according to another aspect, the invention features an adaptive cut-through switching method for a packet switching system receiving and sending data from and to a network via a plurality of ports. This method comprises forwarding received packets to destination ports before the packet has been entirely received as in standard cut-through switching. The validity of the packets is, however, checked after the fact. If it turns out that the packet was invalid, future packets from the port are stored and their validity checked prior to forwarding, a store and forward configuration.
In specific embodiments, the integrity of the packets is checked by reference to check sum information contained in the packets.
In other embodiments, only packets, having source addresses from which invalid packets have been previously received, are placed into a store and forward mode. Alternatively, every packet from a port can be placed on store and forward in response to receiving an invalid packet from that port, regardless of its source address.
The above and other features of the invention including various novel details of construction and combinations of parts, and other advantages, will now be more particularly described with reference to the accompanying drawings and pointed out in the claims. It will be understood that the particular method and device embodying the invention is shown by way of illustration and not as a limitation of the invention. The principles and features of this invention may be employed and various and numerous embodiments without the departing from the scope of the invention.
REFERENCES:
patent: 4296492 (1981-10-01), Hafer
patent: 4382294 (1983-05-01), Beuscher et al.
patent: 5138615 (1992-08-01), Lamport et al.
patent: 5165021 (1992-11-01), Wu et al.
patent: 5274631 (1993-12-01), Bhardwaj
patent: 5307345 (1994-04-01), Lozowick et al.
patent: 5319644 (1994-06-01), Liang
patent: 5402423 (1995-03-01), Van Kersen et al.
patent: 5408469 (1995-04-01), Opher et al.
patent: 5521913 (1996-05-01), Gridley
patent: 5537099 (1996-07-01), Liang
patent: 5682383 (1997-10-01), Dahod et al.
patent: 5926473 (1999-07-01), Gridley
patent: 0 404 337 (1990-12-01), None
Saunders S., “Matrix-Based Switching Revs Up the LAN,”Data Communications, New York, US, 23(5):35-36 (Mar. 21, 1994).
Saunders, S., “Newcomer Takes a New Tack on LAN Switching,”Data Communications, New York, US, 23(13):37-38 (Sep. 21, 1994).
Saunders, S., “LAN Switch Pulls Double Duty,”Data Communications, New York, US, 24(5):37-38 (Apr. 1995).
Saunders, S., “Token Ring Switches Make it to Market,”Data Communications, New York, US, 24(4):49-51 (Mar. 21, 1995).
Kwok, et al., “Cut-Through Bridging for CSMA/CD Local Area Networks,” IEEE Transactions on Comm., vol. 38, No. 7, Jul. 1990, pp. 938-942 (Jul. 7, 1990).
3Com Corporation
McDonnell & Boehnen Hulbert & Berghoff
Ngo Ricky
LandOfFree
Distributed processing ethernet switch with adaptive... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed processing ethernet switch with adaptive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed processing ethernet switch with adaptive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3160234