Method for hashing in a packet network switching system

• US 5,708,659 A
• Filed: 02/16/1995
• Issued: 01/13/1998
• Est. Priority Date: 10/20/1993
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Desai, Sanjay M., Stelliga, Anthony, Rostoker, Michael D., Daane, John P.
• Primary Examiner(s): BLUM, RUSSELL
• Application Number:
  US08/389,601
• Time in Patent Office: 1,062 Days
• Field of Search: 370/58.2, 370/58.3, 370/60, 370/60.1, 370/61, 370/94.1, 370/94.2, 370/94.3, 370/389, 370/392, 370/401, 370/402, 370/466
• US Class Current: 370/392
• CPC Class Codes: G06F 13/128 for dedicated transfers to a network for protocol converters G06F13/387
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5613 Bus (including DQDB)
• CPC Class Codes: H04L 2012/5614 User Network Interface
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5628 Testing
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5653 using the ATM adaptation layer [AAL]
• CPC Class Codes: H04L 2012/5664 Support of Video, e.g. MPEG
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 : Flow control; Congestion control
• CPC Class Codes: H04L 47/11 : Identifying congestion
• CPC Class Codes: H04L 47/263 : Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/43 : Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 49/20 : Support for services
• CPC Class Codes: H04L 49/25 : Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 : Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 : Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3081 : ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/355 : Application aware switches, e.g. for HTTP
• CPC Class Codes: H04L 49/501 : Overload detection
• CPC Class Codes: H04L 49/505 : Corrective measures
• CPC Class Codes: H04L 49/555 : Error detection
• CPC Class Codes: H04L 49/557 : Error correction, e.g. fault recovery or fault tolerance
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/901 : using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9063 : Intermediate storage in different physical parts of a node or terminal
• CPC Class Codes: H04L 49/9078 : using an external memory or storage device
• CPC Class Codes: H04N 19/00 : Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/42 : characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/61 : in combination with predictive coding
• CPC Class Codes: H04N 19/70 : characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 21/2381 : Adapting the multiplex stream to a specific network, e.g. an Internet Protocol [IP] network transmission of MPEG streams over ATM H04L12/5601
• CPC Class Codes: H04N 21/4143 : embedded in a Personal Computer [PC]
• CPC Class Codes: H04N 21/437 : Interfacing the upstream path of the transmission network, e.g. for transmitting client requests to a VOD server flow control in data networks H04L47/10; streaming protocols, e.g. RTP or RTCP, H04L65/65; scheduling or organising the servicing of application requests in data packet switching networks H04L67/60
• CPC Class Codes: H04N 21/4381 : Recovering the multiplex stream from a specific network, e.g. recovering MPEG packets from ATM cells transmission of MPEG streams over ATM H04L12/5601
• CPC Class Codes: H04N 21/4385 : Multiplex stream processing, e.g. multiplex stream decrypting
• CPC Class Codes: H04N 21/4788 : communicating with other users, e.g. chatting arrangements for providing for computer conferences, e.g. chat rooms, to substation in data switching networks H04L12/1813; distributed application using peer-to-peer [P2P] networks H04L67/104
• CPC Class Codes: H04N 21/6402 : Address allocation for clients address allocation in data networks H04L61/50
• CPC Class Codes: H04N 21/64307 : ATM
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections
• CPC Class Codes: H04Q 2213/13034 : A/D conversion, code compression/expansion
• CPC Class Codes: H04Q 2213/13097 : Numbering, addressing
• CPC Class Codes: H04Q 2213/13141 : Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13174 : Data transmission, file transfer
• CPC Class Codes: H04Q 2213/13204 : Protocols
• CPC Class Codes: H04Q 2213/13216 : Code signals, frame structure
• CPC Class Codes: H04Q 2213/13296 : Packet switching, X.25, frame relay
• CPC Class Codes: H04Q 2213/13322 : Integrated circuits
• CPC Class Codes: H04Q 2213/13332 : Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/13353 : Routing table, map memory

Abstract

The port in a packet network switching system that a packet should be associated with is determined by retrieving packet address information for a packet that is to be transmitted. A predetermined number of bits from the packet address information is selected to use a hash key, which is used to compute a table address. The contents of the table at that address are compared with the packet address information. If it matches, the packet is transmitted over the port associated with that particular destination address. If it does not match, the table address is incremented by one, and the contents of the new table location identified by the incremented address are compared with the packet address information. A high speed digital video network apparatus which utilizes the hashing function is implemented on a single integrated circuit chip, and includes a network protocol processing system interconnection, compression/decompression circuits, and encoder/decoder circuits.

Claims

1. In a packet network switching system, a method for hashing to determine a port associated with a destination address comprising the steps of:

retrieving packet address information for a packet to be sent over a network;

selecting a predetermined number of bits from said packet address information to use as a hash key;

computing a table address using said hash key;

comparing the contents of a table corresponding to said table address with said packet address information;

if said contents of the table match said packet address information, identifying a corresponding port associated in the table with said packet address information and sending the packet on said port; and

if said contents of the table do not match said packet address information, incrementing the table address and comparing the contents of the table corresponding to the incremented table address with said packet address information.

2. The method of claim 1 further comprising the step of:

if said contents of the table do not match said packet address information, updating the contents of the table with said packet address information for the packet to be sent over the network.

3. The method of claim 2 wherein said packet address information includes information corresponding to a sender of the packet, said updating step comprising the steps of:

determining the sender of the packet; and

if the sender is not on the table, adding the sender to the table and recording the port that the sender is connected to.

4. The method of claim 1 further comprising the steps of:

storing a pointer which indicates a memory location for the packet information and the port that the packet is to be transmitted on.

5. The method of claim 1 further comprising the steps of:

checking a memory to determine if the memory is filling up; and

executing a priority interrupt if the memory is filled up.

6. The method of claim 5 wherein said executing step comprises the steps of:

jamming the port to cause collisions with packets being transported over the port.

7. The method of claim 6 further comprising the step of:

transmitting a desired packet over the port before the memory fills up.

8. The method of claim 1 wherein said selecting step comprises the step of:

applying a variable window to the address, the variable window including the predetermined number of bits.

9. 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.

10. 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.

11. 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.

12. The method of claim 11 further comprising the step of:

e) determining whether the hash address is empty; and

f) if the hash address is empty, writing to said empty hash address the packet address and the port associated therewith.

13. The method of claim 12 further comprising the step of:

g) if the hash address is not empty, writing over the contents of the hash address with information for the received packet.