Packet switching fabric using the segmented ring with resource reservation control

• US 6,246,692 B1
• Filed: 06/05/1998
• Issued: 06/12/2001
• Est. Priority Date: 02/03/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Chao, Jason, Shih, Cheng-chung, Dai, William
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/092,350
• Time in Patent Office: 1,103 Days
• Field of Search: 370/222, 370/224, 370/258, 370/359, 370/410, 370/419, 370/424, 370/439, 370/438, 370/452, 370/545, 370/447, 370/461, 370/462, 370/463, 370/465, 370/468
• US Class Current: 370/438
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 49/102 using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A packet switching fabric includes a data ring, a control ring, a plurality of network links each coupled to at least one network node, and a plurality of switching devices coupled together by the data ring and the control ring so that the network links can be selectively communicatively coupled. Each of the switching devices includes: a data ring sub-system for transmitting and receiving bursts of data via data ring channels concurrently active on the data ring; a network interface coupled to the data ring sub-system and having at least one network port for transmitting and receiving data packets to and from one of the network links, the network interface also having a packet buffer for storing the data packets, the packet buffer providing bursts of packet data to the data ring sub-system via a plurality of concurrently active packet buffer channels; and a control ring sub-system coupled to the data ring sub-system and to the network interface and being responsive to control messages received from an adjacent one of the devices via the control ring, and operative to develop and transmit the control messages to an adjacent one of the devices via the control ring, the control messages for reserving bandwidth resources used in setting up and controlling the data ring channels and the packet buffer channels, the control ring sub-system also being operative to perform queuing operations for controlling the transfer of the bursts of packet data from the packet buffer to the data ring sub-system.

Claims

1. A packet switching fabric comprising:

means forming a data ring;

means forming a control ring;

means forming a plurality of data communication network links each having at least one network node coupled thereto; and

a plurality of switching devices coupled together by said data ring means and said control ring means and for selectively communicatively coupling said network links, each said switching device including,

data ring processing means for receiving bursts of data from an adjacent one of said devices via at least one of a plurality of data ring channels concurrently active on said data ring, and for transmitting bursts of data to an adjacent one of said devices via at least one of said plurality of data ring channels,

network interface means coupled to said data ring processing means and having at least one network port for transmitting and receiving data packets via one of said network links, said network interface means also having packet buffer means for storing said received data packets, said packet buffer means providing bursts of packet data for transfer to said data ring processing means via a plurality of concurrently active packet buffer channels, and

control ring processing means coupled to said data ring processing means and to said network interface means and being responsive to control messages received from an adjacent one of said devices via said control ring, and operative to develop and transmit control messages to an adjacent one of said devices via said control ring, said control messages for reserving bandwidth resources used in setting up and controlling said data ring channels and said packet buffer channels, said control ring processing means also being operative to perform queuing operations for controlling said transfer of said bursts of packet data from said packet buffer to said data ring processing means via said packet buffer channels.

2. A packet switching fabric as recited in claim 1 wherein:

said received data packets stored in said packet buffer means are stored in memory locations specified by corresponding address pointers, each of said received data packets being received via a corresponding source port of said network ports, each of said received data packets including header information specifying a destination address of a destination node;

each said network port having a port ID value associated therewith; and

said control ring processing means including,

input queuing control means responsive to said destination address specified by said header information of each said received data packet, and operative to identify said port ID value of a destination port of said network ports of a destination one of said devices communicatively coupled to said corresponding destination node,

message termination processing means responsive to said destination port ID value, and operative to generate said control messages for reserving said bandwidth resources, and also operative to generate data ring channel request signals associated with locally active ones of said data ring channels sourced from or traversing said switching device in response to said control messages, said message termination processing means being further operative to generate packet buffer channel request signals associated with said packet buffer channels, and queuing enable signals, and

bandwidth resource managing means responsive to said data ring channel request signals and said packet buffer channel request signals, and operative to set up and allocate a variable amount of bandwidth for said packet buffer channels and said data ring channels,

said input queuing control means also being responsive to said address pointers associated with each said data packet stored in said packet buffer means, and in response to said queuing enable signals, being operative to access said data packets a data burst at a time from said packet buffer means for controlling said transfer of said packet data bursts to said data ring processing means via said packet buffer channels, said input queuing control means also being operative to append each said data burst with block header information including said destination port ID value and an end of packet indicator for indicating whether said data burst is a last data burst of said data packet.

3. A packet switching fabric as recited in claim 2 wherein said control messages include a source request message for requesting setup of a particular one of said data ring channels for transmitting a particular one of said received data packets from said corresponding source port to said corresponding destination port.

4. A packet switching fabric as recited in claim 2 wherein said control messages include sets of associated control messages, each said set of control messages being used to set up and control a particular one of said data ring channels, and also to set up and control a particular one of said packet buffer channels of a source one of said switching devices, said particular data ring channel and said particular packet buffer channel for transmitting a particular one of said data packets stored in said packet buffer of said source device to said corresponding destination port of said corresponding destination device.

5. A packet switching fabric as recited in claim 4 wherein each said control message of each said set includes:

a message field for indicating a message type of said control message;

a source device ID field for carrying a source device ID value identifying said source device of said particular data packet;

a destination device ID field for carrying a destination device ID value identifying said destination device of said particular data packet; and

a destination port ID field for carrying a destination port ID value identifying said destination port of said particular data packet.

6. A packet switching fabric as recited in claim 5 wherein said message types of each said set of control messages include:

a source request message developed by said message termination processing means of said source device and transmitted via said control ring towards said corresponding destination device, said source request message for requesting setup of said particular data ring channel for transmitting said particular data packet from said corresponding source port to said corresponding destination port via said data ring and via participating ones of said switching devices disposed between said source device and said destination device;

a get resource message developed by said message termination processing means of said destination device in response to receiving said associated source request message, said get resource message being transmitted from said destination device via said control ring towards said source device, said get resource message for requesting said participating devices to allocate bandwidth resources for setting up said particular data ring channel;

at least one destination grant message developed by said message termination processing means of said destination device in response to a return of said associated get resource message to said destination device via said control ring, said destination grant message being transmitted from said destination device towards said source device via said control ring, said destination grant message for indicating that said bandwidth resources requested by said associated get resource message are allocated, said destination grant message also requesting said source device to transmit a next burst of data from said packet buffer of said source device to said data processing means of said destination device via said particular data ring channel and said particular packet buffer channel of said source device; and

a release resource message developed by said message termination processing means of said destination device in response to receiving a last of said data bursts from said source device via said particular data ring channel, said release resource message being transmitted from said destination device towards said source device, said release resource message for requesting each said participating device to release said bandwidth previously allocated for said particular data ring channel in response to said associated get resource message.

7. A packet switching fabric as recited in claim 6 wherein said message termination processing means includes a channel rate timer for controlling the rate at which said destination grant messages are transmitted from said destination device towards said source device via said control ring.

8. A packet switching fabric as recited in claim 7 wherein said source request message further includes a packet priority field for requesting that priority be accorded by said message termination processing means of said associated destination device in arbitrating between a present one of said source resource request messages and competing ones of said source request messages.

9. A packet switching fabric as recited in claim 8 wherein said get resource message further includes:

a channel bandwidth field carrying a channel bandwidth value associated with said particular data ring channel;

a source-passed field for indicating whether said get resource message has been propagated past said corresponding source device; and

a bandwidth priority field indicating whether said get resource message is to be given priority in a bandwidth resource arbitration process performed by said bandwidth resource managing means of said participating devices subsequently receiving said get resource message.

10. A packet switching fabric as recited in claim 9 wherein said channel bandwidth value is substantially equal to the bandwidth of said network link connected to said destination port of said particular data packet.

11. A packet switching fabric as recited in claim 9 wherein:

for initial setup of said particular data ring channel,

before said get resource message has passed said source device, said channel bandwidth field carries a value indicative of said bandwidth of said destination output port, and

after said get resource message has passed said source device, said channel bandwidth field carries a value indicative of said bandwidth approved by said source device; and

for incrementally increasing the bandwidth of said particular data ring channel,

after initial channel setup, said channel bandwidth field carries a value indicating that said bandwidth of said particular data ring channel is to be increased.

12. A packet switching fabric as recited in claim 11 wherein said release resource message further includes:

a channel bandwidth field indicating a value associated with said bandwidth to be released;

a source-passed field for indicating whether said release resource message has been propagated past said corresponding source device; and

a clear field for indicating whether said get resource message associated with said release resource message has not been propagated via said control ring past a previous one of said participating devices of said fabric.

13. A packet switching fabric as recited in claim 12 wherein said destination grant message further includes a channel operation field indicating a type of action to be taken with regard to said corresponding particular data ring channel, said actions including new channel setup, no bandwidth change, and incremental bandwidth change.

14. A packet switching fabric as recited in claim 2 wherein said network interface means further includes:

a receive buffer queue for each of said network ports, each said receive buffer queue having an input connected to receive data packets from a corresponding one of said network ports, and an output connected via a bus to said input queuing control means and also to said packet buffer; and

data distribution control means coupled to receive said data bursts received by said data processing means, and having a plurality of outputs each connected to one of said network ports via a corresponding one of a plurality of transmit queue buffers, said data distribution control means including means for reading header information of said data bursts and distributing said data bursts to said corresponding said destination ports.

15. A packet switching fabric as recited in claim 14 wherein said data distribution control means includes a multicast queue for distributing multicast data bursts, having header information specifying multicast addresses, to corresponding multiple ones of said transmit queue buffers for transmission to multiple destination nodes.

16. A packet switching fabric as recited in claim 14 wherein said transmit queue buffers are not large enough to store a whole one of said data packets and wherein cut through packet transfer is implemented through said transmit queue buffers.

17. A packet switching fabric as recited in claim 14 wherein said packet buffer means is implemented by a dynamic RAM memory device.

18. A packet switching fabric as recited in claim 14 wherein at least one of said network links is an Ethernet link having a bandwidth of 10 Mbps.

19. A packet switching fabric as recited in claim 14 wherein at least one of said network links is an Ethernet link having a bandwidth of 100 Mbps.

20. A packet switching fabric as recited in claim 14 wherein at least one of said network links is an Ethernet link having a bandwidth of 1 Gbps.

21. A packet switching fabric as recited in claim 7 wherein said control ring processing means of each said switching device further includes:

means for generating a local device ID value; and

a control ring input interface means which provides control message screening functions including,

reading said message field of a received one of said control messages received via said control ring to determine said message type,

comparing said local device ID value to said source device ID field to determine if a source match exists,

comparing said local device ID value to said destination device ID field to determine if a destination match exists, and

if said message field indicates that said control message is a get resource message or a release resource message,

reading said source passed field of said received control message, and

if said source passed field indicates that said message has not passed said source device, and if no source match or destination match exists, transferring said received control message downstream via said control ring.

22. A packet switching fabric as recited in claim 8 wherein, in response to receiving one of said source request messages wherein said destination device ID field of said received source request message matches said local device ID value, said control ring processing means of each said switching device is further operative to perform steps including:

temporarily storing said received source request message in a source request buffer which is capable of storing additional competing ones of said source request messages;

performing an arbitration process to select one of said source request messages stored in said source request buffer;

transmitting a get resource message, corresponding to said selected source request message, downstream via said control ring to request bandwidth resources for requesting set-up of one of said data ring channels defined by said selected source request message; and

starting a channel acquisition timer which is set to expire after a predetermined maximum time period.

23. A packet switching fabric as recited in claim 7 wherein, in response to a return of said transmitted get resource message to said destination device of origin, said control ring processing means of each said switching device is further operative to perform steps including:

if said channel acquisition timer has expired, generating and transmitting a release resource message downstream via said control ring to release bandwidth reserved by said returned get resource message; and

if said channel acquisition timer has not expired, turning on said data ring channel specified by said returned get resource message, transmitting a destination grant message to said source device via said control path to request transmission of a first burst of packet data, and resetting said channel acquisition timer.

24. A packet switching fabric as recited in claim 11 wherein, in response to a return of said transmitted get resource message to said destination device of origin, said control ring processing means of each said switching device is further operative to perform steps including:

determining whether said channel bandwidth field of said returned get resource message specifies initial set-up of a data ring channel or incremental increase of an existing data ring channel;

if said channel bandwidth field of said get resource message specifies initial set-up of a data ring channel,

determining whether said channel acquisition timer has expired,

if said channel acquisition timer has expired, generating and transmitting a release resource message downstream via said control ring to release bandwidth reserved by said returned get resource message,

if said channel acquisition timer has not expired,

providing a data ring channel request signal to said bandwidth resource managing means requesting local activation of said data ring channel specified by said get resource message,

transmitting a destination grant message downstream via said control path to confirm bandwidth allocation for said new data ring channel and also to request a first burst of data, and

resetting said channel acquisition timer; and

if said channel bandwidth field of said get resource message specifies incremental increase of an existing data ring channel,

increasing the rate of said channel rate timer,

determining whether said maximum channel rate has been reached,

if said maximum channel rate has not been reached, confirming said rate increase by transmitting a destination grant signal, and

transmitting a get resource message with its channel bandwidth field carrying a value indicating that said bandwidth of said particular data ring channel is to be increased.

25. A packet switching fabric as recited in claim 13 wherein, in response to receiving a burst of data, said control ring processing means of each said switching device is further operative to perform steps including:

reading said block header of said burst of data to determine whether said received burst of packet data is the last data burst of said data packet;

if said burst of data is not said last burst of data,

waiting for said channel rate timer to expire,

determining whether said channel rate timer has been increased since receiving a previous burst of data,

if said channel rate has not been increased since receiving a previous burst of data, sending a destination grant message with said channel operation field indicating no bandwidth change, to request a next burst of data, and restarting said channel rate timer,

if said channel rate has been increased since receiving said previous burst of data, sending a destination grant message with said channel operation field indicating incremental bandwidth to confirm said increased bandwidth, and to request a next burst of data, and restarting said channel rate timer.

26. A packet switching fabric as recited in claim 13 wherein, in response to the return of a destination grant message to said destination device of origin, said control ring processing means is further operative to perform steps including:

reading said channel operation field of said destination grant message;

if said channel operation field indicates an incremental bandwidth change, confirming said rate increase by increasing a corresponding bandwidth counter;

if said destination grant message is confirming a new channel set-up, determining whether said maximum channel rate has been reached; and

if said maximum channel rate has not been reached, transmitting a get resource message with said channel bandwidth field indicating a request for an increment in bandwidth.

27. A packet switching fabric as recited in claim 22 wherein, in response to receiving a get resource message, said control ring processing means of each said switching device is further operative to perform steps including:

if said source match exists,

temporarily storing said get resource message in a control message buffer,

reading said channel bandwidth field of said get resource message to determine said channel bandwidth value;

providing a packet buffer channel request signal to said bandwidth resource managing means requesting packet buffer channel bandwidth specified by said channel bandwidth value, and waiting for said bandwidth resource managing means to allocate said requested packet biiffer channel bandwidth;

providing a data ring channel request signal to said bandwidth resource managing means requesting data ring channel bandwidth specified by said channel bandwidth value, and waiting for said bandwidth resource managing means to allocate said requested data ring channel bandwidth;

determining whether a release resource message has been received

if a release resource message has not been received, transmitting a get resource to said destination device via said control ring.

28. A method of manufacturing a packet switching fabric comprising the steps of:

forming a data ring;

forming a control ring; and

providing a plurality of switching devices coupled together by said data ring means and said control ring means so that a plurality of data communication network links, each having at least one network node coupled thereto, can be selectively communicatively coupled, each said switching device being fabricated by performing steps including,

providing data ring processing means for receiving bursts of data from an adjacent one of said devices via at least one of a plurality of data ring channels concurrently active on said data ring, and for transmitting bursts of data to an adjacent one of said devices via at least one of said plurality of data ring channels,

providing network interface means coupled to said data ring processing means and having at least one network port for transmitting and receiving data packets via one of said network links, said network interface means also having packet buffer means for storing said received data packets, said packet buffer means providing bursts of packet data for transfer to said data ring processing means via a plurality of concurrently active packet buffer channels, and

providing control ring processing means coupled to said data ring processing means and to said network interface means and being responsive to control messages received from an adjacent one of said devices via said control ring, and operative to develop and transmit said control messages to an adjacent one of said devices via said control ring, said control messages for reserving bandwidth resources used in setting up and controlling said data ring channels and said packet buffer channels, said control ring processing means also being operative to perform queuing operations for controlling said transfer of said bursts of packet data from said packet buffer to said data ring processing means via said packet buffer channels.