Method for hashing in a packet network switching system

A method of hashing packets in a packet network switching system including a plurality of ports, each of the packets including a packet header having sender information indicative of the sender of the packet and recipient information indicative of the intended recipient of the packet, each of the ports being associated with a sender for receiving packets from the sender and with a recipient for transmitting packets to the recipient, the method comprising the steps of:

• a) storing a list of known recipients;
• b) monitoring the plurality of ports for packets received at the ports;
• c) extracting the packet header from a received packet;
• d) storing the received packet in a packet memory;
• e) storing a pointer, corresponding to the stored received packet, in a pointer memory, the stored pointer indicating a location in the packet memory at which the corresponding received packet is stored;
• f) comparing the recipient information of the packet header of the received packet with the list of known recipients to determine if the intended recipient is on the list;
• g) if the intended recipient is not on the list, broadcasting the received packet to the recipients via all of the ports;
• h) if the intended recipient is on the list, transmitting the received packet to the intended recipient by:
• (1) determining which of the ports is associated with the intended recipient;
• (2) accessing the pointer stored in the pointer memory;
• (3) retrieving the received packet stored in the packet memory corresponding to the accessed pointer;
• and
• (4) transmitting the received packet retrieved from the packet memory to the intended recipient via the associated port;
• and
• i) updating the list of known recipients with the information in the packet header by:
• (1) recording the number of received packets addressed to each of the known recipients on the list;
• and
• (2) deleting from the list the known recipients which have the fewest received packets address thereto.

A method of hashing packets in a packet network switching system including a plurality of ports, each of the packets including a packet header having sender information indicative of the sender of the packet and recipient information indicative of the intended recipient of the packet, each of the ports being associated with a sender for receiving packets from the sender and with a recipient for transmitting packets to the recipient, the method comprising the steps of:

• a) storing a list of known recipients;
• b) monitoring the plurality of ports for packets received at the ports;
• c) extracting the packet header from a received packet;
• d) storing the received packet in a packet memory;
• e) storing a pointer, corresponding to the stored received packet, in a pointer memory, the stored pointer indicating a location in the packet memory at which the corresponding received packet is stored;
• f) comparing the recipient information of the packet header of the received packet with the list of known recipients to determine if the intended recipient is on the list;
• g) if the intended recipient is not on the list, broadcasting the received packet to the recipients via all of the ports;
• h) if the intended recipient is on the list, transmitting the received packet to the intended recipient by:
• (1) determining which of the ports is associated with the intended recipient;
• (2) accessing the pointer stored in the pointer memory;
• (3) retrieving the received packet stored in the packet memory corresponding to the accessed pointer;
• and
• (4) transmitting the received packet retrieved from the packet memory to the intended recipient via the associated port;
• i) checking the pointer memory for any stored pointers;
• if there is a stored pointer:
• (1) determining whether the port associated with the intended recipient of the receive packet corresponding to the stored pointer, is clear;
• and
• (2) determining whether the packet memory is filling up with stored received packets;
• j) if the packet memory is not filling up:
• (1) storing the received packet in the packet memory;
• and
• (2) returning to step checking the pointer memory for any other stored pointers;
• and
• k) if the associated port is clear and if the packet memory is filling up:
• (1) executing a priority interrupt for the associated port;
• and
• (2) transmitting the received packet to the intended recipient via the associated port.

A method of hashing a packet received by a network switching system including a plurality of ports each associated with a known address, the known addresses being stored in a table, the packet including a header containing a packet address, the method comprising the steps of:

• a) comparing the packet address to one of the known addresses to determine whether the packet address matches the known address by:
• (1) selecting a hash key from a subset of the address bits contained in the packet header;
• (2) computing a hash address in the table based upon the hash key;
• (3) comparing the hash address to the packet address to determine whether there is a match;
• and
• (4) if there is no match, incrementing the hash address and repeating steps (2) and (3);
• b) if the packet address matches the known address, transmitting the received packet to the port associated with the matching known address;
• c) if the packet address does not match the known address, comparing the packet address to another one of the known address to determine whether the packet address matches the other known address, and repeating step b;
• and
• d) if the packet address does not match any of the known addresses on the list, broadcasting the received packet to all of the ports.