Apparatus and method for a network router

• US 5,991,817 A
• Filed: 09/06/1996
• Issued: 11/23/1999
• Est. Priority Date: 09/06/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Collins, Crosswell C., Buell, Eric R., Rowett, Kevin J.
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): PIERCE, IVAN
• Application Number:
  US08/709,178
• Time in Patent Office: 1,173 Days
• Field of Search: 370/392, 370/85.13, 370/402, 370/94.1, 340/825.03, 395/800, 709/238, 709/239-244, 709/212, 709/250
• US Class Current: 709/250
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A router is integrated onto a single silicon chip and includes an internal bus that couples multiple data receive and transmit channels to a central processing unit. The channels each have an external interface for connecting to different LAN or WAN networks. The serial channels are convertible into one or more time division multiplexed (TDM) channels. A time slot assigner (TSA) assembles and disassembles data packets transferred in TDM formats, such as ISDN. The serial channels are used for separately processing data packets in each TDM time slot. The TSA is programmable to operate with different TDM formats. A single direct memory access controller (DMAC) is coupled to each serial channel and an Ethernet channel and conducts data transfers on the internal router bus through a common port. The DMAC uses a novel bus protocol that provides selectable bandwidth allocation for each channel. The router architecture includes different interface circuitry which is also integrated onto the silicon chip. The interface circuitry includes user definable input/output (I/O) pins with programmable pulse width detection. The user definable I/O provides synchronous and asynchronous interfacing to peripheral devices with different timing constraints. The interface circuitry also includes a DRAM controller having a programmable timing control circuit that operates with memory devices having different timing and memory block sizes.

Claims

1. A network router, comprising:

multiple channels each coupled to an associated network that transfers data packets having an associated network protocol, the multiple channels each independently transferring the data packets with the associated network;

an internal bus;

a CPU coupled to the internal bus that converts the data packets between each associated network protocol;

a master DMAC coupled between each one of the multiple channels and the internal bus for routing the data packets between the multiple channels and the internal bus, the DMAC providing a common interface between the multiple channels and the internal bus and allocating independently of the CPU and without communication over the internal bus with the CPU programmable percentages of bandwidth on the internal bus and selectable latency to each of the multiple channels;

the multiple channels, central processing unit, internal bus and DMAC all integrated onto a single silicon chip.

2. A router according to claim 1 wherein the DMAC includes time slot assignment registers associated with the bandwidth time slots and assignable to any one of the multiple channels and controllers associated with each one of the channels that identify the number of bytes contained in the channels, the DMAC changing requested priority on the internal bus for the channels according to the number of bytes identified in the channels by the associated controllers in the DMAC.

3. A router according to claim 1 wherein the DMAC includes the following:

DMA control circuitry coupled between the multiple channels and the internal bus for controlling data packet transfers between each one of the multiple channels and the internal bus; and

a set of DMA registers associated with each one of the multiple channels for storing DMA context data, the DMA context data for the multiple channels currently transferring data packets swapped into the DMA control circuitry.

4. A router according to claim 3 wherein each set of DMA registers includes one register subset controlling transmission of the data packets from the internal bus to the associated channels and one register subset controlling reception of the data packets from the associated channels to the internal bus.

5. A router according to claim 4 wherein each set of DMA registers includes the following:

a current address counter containing an address on the internal bus used for transferring the data packets;

a current descriptor pointer containing an address pointing to a buffer descriptor having a memory address for the data packets;

a DMA control and status/byte count register holding DMA status data and the size of the data packet; and

a DMA size count register indicating what portion of the data packet has been transferred.

6. A router according to claim 3 including a memory coupled to the internal bus for storing the data packets and buffer descriptors associated the data packets, the buffer descriptors exchanged with the DMA context data in the DMA registers, the buffer descriptors each including the following:

DMA control and status data,

a size count for the associated data packets,

a data buffer pointer identifying an address location in the memory for the associated data packets, and

a next descriptor pointer identifying an address in memory for a next buffer descriptor.

7. A router according to claim 1 wherein the DMAC includes staging registers coupled between each one of the multiple channels and the internal bus, the staging registers holding multiple byte blocks of the data packets and transferring the blocks on arbitrary byte boundaries.

8. A router according to claim 7 wherein the DMA controller includes the following:

bus interface circuit coupled between the internal bus and the staging registers;

a channel multiplexer coupled to the staging registers for selectively receiving data packets from any one of the multiple channels;

a channel selector coupled to the staging registers for selectively outputting the data packets from the internal bus to any one of the multiple channels.

9. A router according to claim 8 wherein the staging registers include a receive staging register coupled to the channel multiplexer and a transmit staging register coupled to the channel selector, the receive staging register receiving some of the data packets from any of the multiple channels at the same time that the transmit staging registers transmit some of the data packets to the multiple channels.

18. A router according to claim 1 including interface circuitry coupled to the internal bus and integrated onto the silicon chip.

19. A router according to claim 18 wherein the interface circuitry includes at least one UART interface circuit.

20. A router according to claim 18 wherein the interface circuitry includes at least one PC card controller.

26. A router according to claim 1 including an arbiter coupled to the internal bus for controlling bus transactions, the arbiter pregranting a second bus transaction while the internal bus is currently conducting a first bus transaction.

27. A router according to claim 1 including the following:

a CPU bus coupled to the CPU;

an internal CPU memory coupled to the CPU bus; and

an in-circuit emulator coupled between the internal bus, DMAC and the CPU bus, the in-circuit emulator selectively tracing signals on the CPU bus and signals the DMAC not accessible by external I/O pins according to preselected CPU bus conditions and DMAC signaling conditions.

28. A router according to claim 1 including a microboot ROM coupled to the internal bus and integrated onto the silicon chip, the microboot ROM storing boot code for initializing the router.

29. A router according to claim 28 including decode logic for selectively booting the router from one of the microboot ROM and a memory device connected externally to the router chip.

10. A network router, comprising:

multiple channels each coupled to an associated network that transfers data packets using an associated network protocol;

an internal bus;

a CPU coupled to the internal bus that converts data packets between each network protocol; and

a DMAC coupled to each one of the multiple channels and the internal bus for routing the data packets between the multiple channels and the internal bus;

the multiple channels configurable to receive and transmit both serial data and TDM data on selectable TDM channels in a time division multiplexed format.

11. A router according to claim 10 wherein each one of the multiple channels includes a receive path and a transmit path, each path including a control circuit for translating the data packets between one of a serial and a parallel format and a FIFO for holding the data packets.

12. A router according to claim 10 wherein the channels include a shift register that selectively transfers data packets both least significant bit first and most significant bit first.

13. A router according to claim 10 wherein the multiple channels include at least one Ethernet channel coupled to an Ethernet network.

14. A router according to claim 10 including a serial line multiplexer coupled between the serial channels and the associated networks, the serial line multiplexer receiving and transmitting the data packets in either a serial data steam or a time division multiplexed data stream independently of the CPU.

15. A router according to claim 14 including a time slot assigner coupled to the serial line multiplexer, the time slot assigner demultiplexing data packets from different time slots in the time division multiplexed data stream into different serial channels and multiplexing the data packets from the multiple serial channels into a single time division multiplexed data stream.

16. A router according to claim 15 wherein the time slot assigner includes a receiver circuit having

a receiver memory for holding receive channel select entries;

a receive current entry counter coupled to the receiver memory;

a receive time slot size counter coupled between the receiver memory and the receive current entry counter;

receive serial channel registers associated with each one of the serial channels; and

a receive selector coupled between the receiver memory and the receive serial channel registers, the receive selector selectively loading portions of the time division multiplexed data stream into different serial channels according to the receive channel select entries in the receiver memory.

17. A router according to claim 16 wherein the time slot assigner circuit includes a transmitter circuit having

a transmitter memory for storing transmit channel select entries;

a transmit current entry counter coupled to the transmitter memory;

a transmit time slot size counter coupled between the transmitter memory and the transmit current entry counter;

transmit serial channel registers associated with each one of the serial channels;

a transmit channel selector coupled between the transmit memory and the transmit serial channel registers, the transmit selector selectively outputting portions of the data packets from the transmit serial channel registers according to the transmit channel select entries in the transmitter memory; and

a multiplexer coupled to the transmit serial channel registers for multiplexing the data packets from the serial channels into the time division multiplexed data stream according to the transmit channel select entries in the transmitter memory.

21. A network router, comprising:

multiple channels each coupled to an associated network that transfers data packets using an associated network protocol;

an internal bus;

a CPU coupled to the internal bus that converts data packets between each network protocol;

a DMAC coupled to each one of the multiple channels and the internal bus for routing the data packets between the multiple channels and the internal bus; and

interface circuitry including a user definable I/O circuit having programmable input pulse width detection for detecting and converting different asynchronous input pulse widths into uniform width synchronous output pulses.

22. A router according to claim 21 wherein the user definable I/O circuit comprises the following:

an external pin configurable for receiving an input signal or transmitting an output signal;

a signal synchronizer coupled to the external pin for synchronizing the input signal; and

a pulse width detection circuit selectively coupled to both the external pin and the signal synchronizer for selectively detecting the pulse width of the input signal.

23. A router according to claim 22 wherein the user definable I/O circuit includes control registers for selectively enabling the external pin as an input or output, selectively synchronizing the input signal, selectively detecting variable pulse widths of the input signal and selectively latching the input and output signals.

24. A router, comprising:

multiple channels each coupled to an associated network that transfers data packets using an associated network protocol;

an internal bus;

a CPU coupled to the internal bus that converts data packets between each network protocol;

a DMAC coupled to each one of the multiple channels and the internal bus for routing the data packets between the multiple channels and the internal bus; and

multiple blocks of memory having different timing control signals; and

a memory controller coupled between the internal bus and the multiple blocks of memory, the memory controller programmable for generating selectable refresh and memory access timing for the different timing control signals for each one of the multiple blocks of memory.

25. A router according to claim 24 wherein the memory controller includes the following:

a bus interface unit for interfacing to the internal bus;

a decoder coupled to the bus interface unit for determining which block of memory is selected based on an internal bus address, a memory block base address; and

a block size;

a programmable timing circuit coupled to the decoder for individually generating the timing signals for each one of the multiple blocks of memory.

30. A network router, comprising:

multiple serial channels and at least one Ethernet channel all independently transferring data packets between associated network systems having network protocols;

an internal bus;

a central processing unit coupled to the internal bus for converting the data packets between the network protocols;

a memory coupled to the internal bus, the memory storing the data packets and associated buffer descriptors, the buffer descriptors each including DMA context data and a pointer to an associated one of the data packets; and

a single DMAC coupled between all the channels and the internal bus independently of the CPU that provides a common interface between the multiple serial channels and the internal bus;

the DMAC including a DMA control circuit for conducting data packet transfers between the memory and the channels and a set of DMA registers associated with each one of the channels holding DMA context data selectively swapped into the DMA circuitry independently of the CPU according to which channels are currently transferring data packets.

31. A router according to claim 30 wherein the DMAC includes staging registers coupled between each one of the channels and the internal bus for transferring the data packets in multiple byte blocks between the memory and the multiple channels on arbitrary byte boundaries according to the pointer in the buffer descriptors.

32. A router according to claim 31 wherein the serial channels are each convertible into a TDM channel for transmitting and receiving the data packets in a time division multiplexed format.

33. A router according to claim 32 wherein each one of the serial channels includes an independently controllable receive path and a transmit path, each path including a control circuit for translating the data packets between one of a serial and a parallel format and a FIFO for temporarily holding the data packets.

34. A router according to claim 33 wherein the channels each selectively transfer the data packets least significant bit first or most significant bit first.

35. A router according to claim 34 including a time slot assigner coupled to the multiple serial channels, the time slot assigner demultiplexing data packets from different time slots in a time division multiplexed data stream into different serial channels and multiplexing data packets from different serial channels into a single time division multiplexed data stream.

36. A method for arbitrating bus transactions for data packets on an internal bus in a router coupled to multiple processing elements, comprising:

requesting the internal bus with a first processing element;

granting the internal bus to the first processing element;

conducting a first bus transaction with the first processing element after being granted the internal bus;

requesting the internal bus with a second processing element while the first processing element is conducting the first bus transaction;

pregranting the internal bus to the second processing element while the first processing element is conducting the first bus transaction; and

conducting a second bus transaction with the second processing element immediately after the first processing element has indicated completion of the first bus transaction; and

providing a DMAC that serves as common interface between the first and second processing elements and the internal bus.

37. A method according to claim 36 including the step of automatically parking the granting of the internal bus on the first processing element when no bus requests are generated from any of the processing elements.

38. A method according to claim 37 including conducting internal bus transactions with the first processing element without requesting the internal bus when the bus grant is parked on the first processing element.

39. A method according to claim 38 including the following steps:

continuously requesting the internal bus with both the first and second processing element; and

repeatedly switching granting and pregranting the internal bus between the first processing element and the second processing element; and

repeatedly conducting bus transactions with the first processing element and then the second processing element according to the grants and pregrants.

40. A method according to claim 39 including the following steps:

requesting back-to-back bus transactions with the first processing element where the first processing element requests a second bus transaction while conducting the first internal bus transaction; and

granting back-to-back bus transactions to the first processing element only when no other processing elements in the router request the internal bus during the first internal bus transaction.

41. A method for conducting bus transactions on an internal bus in a router, comprising:

coupling the internal bus through a first channel to a first network transferring data packets using a first network protocol;

coupling the internal bus through a second channel to a second network transferring data packets using a second network protocol;

allocating selectable percentages of internal bus bandwidth to the first and second channel by assigning a first set of bandwidth time slots to the first channel and assigning a second set of bandwidth time slots to the second channel;

transferring data packets from the first network through the first channel to the internal bus during the first set of time slots;

converting the data packets from the first network protocol into the second network protocol;

transferring converted data packets from the internal bus through the second channel to the second network during the second set of time slots; and

transmitting data packets at a higher priority during each one of the time slots when the stored data packet bytes are the last bytes in one of the data packets or when the data packets have been held in the channels for a predetermined amount of time; and

providing a DMAC that serves as a common interface for coupling the first and second channel to the internal bus.

42. A method according to claim 41 including increasing priority of the first channel by assigning the first channel more time slots than the second channel.

43. A method according to claim 41 including reducing latency in the first channel by assigning the first channel time slots located throughout the internal bus bandwidth.

44. A method according to claim 41 including the following steps:

receiving data packet bytes in each of the channels; and

transmitting data packets during each one of the time slots when a predetermined number of the data packet bytes are stored in the channels, when the stored data packet bytes are the last bytes in one of the data packets or when the data packets have been held in the channels for a predetermined amount of time.

45. A method according to claim 41 including selectively transferring the data packets between the first and second channels and the internal bus most significant bit first or least significant bit first.

46. A method according to claim 41 including transferring data packets in multiple byte blocks between the first and second channel and the internal bus on arbitrary byte boundaries.