Method and apparatus for buffering data within stations of a communication network

• US 5,313,582 A
• Filed: 04/30/1991
• Issued: 05/17/1994
• Est. Priority Date: 04/30/1991
• Status: Expired due to Term

• Current Assignee: Standard Microsystems Corporation (Microchip Technology Incorporated)
• Original Assignee: Standard Microsystems Corporation (Microchip Technology Incorporated)
• Inventors: Hendel, Ariel, Brinkerhoff, Kenneth W.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): DINH, DUNG C
• Application Number:
  US07/693,637
• Time in Patent Office: 1,113 Days
• Field of Search: 395/250, 370/60, 370/94.1
• US Class Current: 710/56
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Method and apparatus are disclosed for buffering data packets in a data communication controller. The communication controller is interfaced with a host processor and includes a control unit for accessing a communication medium. Each data packet to be transmitted or received is assigned a packet number. Packet number assignment is carried out by a memory management unit within the communication controller which dynamically allocates to each assigned packet number one or more pages in a data packet buffer memory for the storage of the corresponding data packet. Upon issuing the assigned packet number, the physical addresses of the allocated pages of data packet buffer memory storage space are generated in a manner transparent to both the host processor and the control unit. Upon completion of each data packet loading operation, the corresponding packet number is stored in a packet number queue maintained for subsequent retrieval in order to generate the physical addresses at which the corresponding data packet has been stored. Also disclosed is a mechanism for automatically generating transmit interrupts to the host processor upon the completion of any preselected number of data packet transmissions determined by the host processor.

Claims

1. A method of buffering data packets using a data communication controller which is interfaced with a processor and includes a control means for accessing a communication medium, said method comprising the steps:

(a) providing a data packet storage means managed by said data communication controller independent of said processor, said data packet storage means including a plurality of data page storage locations for storage of one or more data packets;

(b) said data communication controller assigning a packet number to a data packet to be stored in one or more of said data page storage locations;

(c) said data communication controller storing said data packet in one or more of said data page storage locations, by

(1) said processor generating a first set of linear addresses ranging from a first minimum address value to a first maximum address value, and

(2) said data communication controller using said packet number assigned to said data packet in step (b) and said first set of linear addresses to generate a corresponding set of physical addresses which define the physical location of said one or more data page storage locations in said data packet storage means;

(d) said data communication controller maintaining a packet number queue in said data communication controller, for storing one or more of said packet numbers, each said packet number corresponding to one said stored data packet;

(e) said data communication controller storing in said packet number queue, said packet number assigned to said stored data packet in step (b);

(f) sad data communication controller retrieving said stored packet number from said packet number queue; and

(g) said data communication controller retrieving said data packet stored in said one or more data page storage locations during step (c), by

(1) said control means generating a second set of linear addresses ranging from a second minimum address value to a second maximum address value, and

(2) said data communication controller using said packet number assigned to said data packet in step (b) and said set of linear addresses to generate a corresponding set of physical addresses which define the physical location of said one or more data page storage locations in said data packet storage means.

2. The method of claim 1, where in step (d), said packet number queue has a plurality of storage locations including an insert storage location at which each packet number is inserted into said packet number queue, and a removal storage location from which each packet number is removed from said packet number queue.

3. The method of claim 2, wherein step (e) comprises said data communication controller storing said assigned packet number in said insert storage location of said packet number queue, and step (f) comprises said data communication controller removing said packet number from said removal storage location of said packet number queue.

4. The method of claim 3, wherein step (b) further comprises

(1) said data communication controller determining the number of data page storage locations required to store said data packet,

(2) said data communication controller allocating said required number of free data page storage locations for storing said data packet, and

(3) said data communication controller assigning said packet number to each of said allocated data page storage locations.

5. The method of claim 1, which further comprises said processor maintaining independent of said data communication controller, a first data packet queue for storing one or more data packets to be transferred from said processor to said communication medium by way of said data communication controller, and wherein step (c) further comprises

(3) said processor transferring said data packet from said first data packet queue to said data communication controller, and said data communication controller transferring said data packet to said one or more data page storage locations specified by said generated set of physical addresses.

6. The method of claim 1, wherein step (g) further comprises

(3) said data communication controller transferring said data packet from said one or more data page storage locations specified by said generated set of physical addresses, to said control means for transfer to said communication medium.

7. The method of claim 6, which further comprises after step (g),

(4) said data communication controller providing said generated set of physical addresses to said data packet storage means, and

(5) said data communication controller writing transmit status data from said control means, into said data page storage locations specified by said generated set of physical addresses.

8. The method of claim 7, which further comprises after steps (4) and (5),

(6) said data communication controller providing said generated set of physical addresses to said data packet storage means, and

(7) said data communication controller reading said transmit status data from said data page storage locations specified by said generated set of physical addresses.

9. The method of claim 5, which further comprises said processor maintaining independent of said data communication controller, a second data packet queue for storing one or more data packets transferred to said processor from said communication medium, and wherein step (c) further comprises

(3) said control means transferring said data packet to said data communication controller, and said data communication controller transferring said data packet to said one or more data page storage locations specified by said generated set of physical addresses.

10. The method of claim 9, wherein step (g) further comprises

(3) said data communication controller transferring said data packet from said one or more data page storage locations specified by said generated set of physical addresses, to said processor.

11. The method of claim 10 which further comprises after step (c),

(4) said data communication controller providing said generated set of physical addresses to said data packet storage means, and

(5) said data communication controller writing receive status data from said control means, into one or more of said data page storage locations specified by said generated set of physical addresses.

12. The method of claim 11, which further comprises after step (4) and (5),

(6) said data communication controller providing said generated set of physical addresses to said data packet storage means, and

(7) said data communication controller reading said receive status data from said one or more data page storage locations specified by said generated set of physical addresses.

13. A method of buffering data packets using a data communication controller which is interfaced with a processor and which includes a control means for accessing a communication medium, said method comprising the steps:

(a) providing a data packet storage means managed by said data communication controller independent of said processor, said data packet storage means including a plurality of data page storage locations for storing one or more transmit data packets and one or more receive data packets;

(b) said data communication controller maintaining a transmit packet number queue, for storing one or more packet numbers, each said packet number stored in said transmit packet number queue corresponding to one said transmit data packet;

(c) said data communication controller maintaining a receive packet number queue for storing one or more packet numbers, each said packet number stored in said receive packet number queue corresponding to one said receive data packet;

(d) said data communication controller assigning a first packet number to a transmit data packet to be stored in one or more of said data page storage locations;

(e) said data communication controller storing said transmit data packet in one or more of said data page storage locations by

(1) said processor generating a first set of linear addresses ranging from a minimum address value to a maximum address value, and

(2) said data communication controller using said first packet number assigned to said transmit data packet in step (d) and said first set of linear addresses so as to generate a first set of physical addresses which defines the physical location of said one or more data page storage locations in which said transmit data packet is stored in said data packet storage means;

(f) said data communication controller storing in said transmit packet number queue, said first packet number assigned to said stored transmit data packet during step (d);

(g) said data communication controller assigning a second packet number to a receive data packet to be stored in one or more said data storage locations;

(h) said data communication controller storing said receive data packet in one or more of said data page storage locations, by

(1said processor generating a second set of linear addresses ranging from a minimum address value to a maximum address value, and

(2) said data communication controller using said second packet number assigned to said receive data packet in step (g) and said second set of linear addresses so as to generate a second set of physical addresses which defines the physical location of said one or more data page storage locations in which said receive data packet is stored in said data packet storage means;

(i) said data communication controller storing in said receive data packet number queue, said second packet number assigned to said received data packet during step (g);

(j) said data communication controller retrieving said first packet number from said transmit packet number queue;

(k) said data communication controller retrieving said transmit data packet from said data packet storage means, by

(1) said control means generating said first set of linear addresses, and

(2) said data communication controller using said first packet number assigned to said transmit data packet in step (d) and said first set of linear addresses so as to generate said first set of physical addresses which defines the physical location of said one or more data page storage locations in which said transmit data packet is stored in said data packet storage means, and after retrieving said transmit data packet, said data communication controller providing said retrieved transmit data packet to said control means;

(l) said data communication controller retrieving said second packet number from said receive packet number queue; and

(m) said data communication controller retrieving said receive data packet from said data packet storage means, by

(1) said processor generating said second set of linear addresses, and

(2) said data communication controller using said second packet number assigned to said receive transmit data packet in step (g) and said second set of linear addresses so as to generate said second set of physical addresses which defines the physical location of said one or more data page storage location in which said receive data packet is stored in said data packet storage means; and

providing said retrieved receive data packet to said processor.

14. The method of claim 13, where in step (b) said transmit packet number queue has a plurality of storage locations including a first insert storage location at which said first packet number is inserted into said transmit packet number queue, and a first removal storage location from which said first packet number is removed from said transmit packet number queue, and where in step (c) said receive packet number queue has a plurality of storage locations including a second insert storage location at which said second packet number is inserted into said receive packet number queue, and a second removal storage location from which said second packet number is removed from said receive packet number queue.

15. The method of claim 14, wherein step (f) comprises said data communication controller storing said first packet number in said first insert storage location, and wherein step (j) comprises said data communication controller removing said first packet number from said first removal storage location.

16. The method of claim 15, wherein step (i) comprises said data communication controller storing said second packet number in said second insert storage location, and wherein step (l) comprises said data communication controller removing said second packet number from said second removal storage location.

17. The method of claim 16, wherein step (d) further comprises

(1) said data communication controller determining the number of data page storage locations required to store said transmit data packet;

(2) said data communication controller allocating said required number of free data page storage locations for storing said transmit data packet and

(3) said data communication controller assigning said first packet number to each said allocated data page storage location; and

wherein step (g) further comprises;

(1) said data communication controller determining the number of data page storage locations required to store said receive data packet,

(2) said data communication controller allocating said required number of free data page storage locations for storing said receive data packet, and

(3) said data communication controller assigning said second packet number to each said allocated data page storage location.

18. The method of claim 13, which further comprises said processor maintaining independent of said data communication controller, a transmit data packet queue for storing one or more transmit data packets to be transferred to said communication medium, and wherein step (e) further comprises

(3) said processor transferring said transmit data packet from said transmit data packet queue to said data communication controller and said data communication controller transferring said transmit data packet, to said one or more data page storage locations specified by said generated first set of physical addresses.

19. The method of claim 13, which further comprises after step (k),

(3) said data communication controller providing said generated first set of physical addresses to said data packet stored means, and

(4) said data communication controller writing transmit status data from said control means, into one or more of said data page storage locations specified by said generated first set of physical addresses.

20. The method of claim 19, which further comprises after steps (3) and (4),

(5) said data communication controller providing said generated first set of physical addresses to said data packet storage means, and

(6) said processor reading said transmit status data from said one or more data page storage locations specified by said generated first set of physical addresses.

21. The method of claim 13, which further comprises said processor maintaining independent of said data communication controller, a receive data packet queue for storing one or more receive data packets transferred from said communication medium to said processor, and wherein step (h) further comprises

(3) said data communication controller transferring said receive data packet from said control means, to said one or more data page storage locations specified by said generated second set of physical addresses.

22. The method of claim 21, wherein step (k) further comprises

(6) said data communication controller providing said corresponding second set of physical addresses to said data packet storage means, and

(7) said data communication controller transferring one said receive data packet from said one or more data page storage locations specified by said corresponding second set of physical addresses, to said processor for transfer to said receive data packet queue.

23. The method of claim 21, which further comprises after step (m),

(3) said data communication controller providing said second corresponding set of physical addresses to said data packet storage means, and

(4) said data communication controller writing receive status data from said control means, into one or more of said data page storage locations specified by said corresponding second set of physical addresses.

24. The method of claim 23, which further comprises after steps (3) and (4),

(5) said data communication controller providing said corresponding second set of physical addresses to said data packet storage means, and

(6) said control means reading said receive status data from said one or more data page storage locations specified by said generated second set of physical addresses.

25. A data communication controller for interfacing with a processor and for operably associating with a data packet storage means having a plurality of data page storage locations for storing one or more data packets, said data communication controller comprising:

a control means for accessing a communication medium;

memory management means for managing said data packet storage means independent of said processor by assigning a packet number to each data packet to be stored in said data packet storage means and allocating one or more of said data page storage locations for storing each said data packet to be stored;

linear address bit receiving means for receiving one or more sets of linear address bits from said processor or said control means, each said set of linear address bits corresponding to one said data packet to be stored and ranging from a minimum address value to a maximum address value;

physical address generating means for generating a set of physical addresses for each data packet to be stored in said data packet storage means, by using the data packet number assigned to said data packet to be stored and said set of linear address bits corresponding to said data packet to be stored, each set of physical addresses corresponding to one or more data page storage locations in said data packet storage means and providing access to said one or more data page storage locations;

data packet transfer means for transferring data packets between said processor and said data packet storage means, and for transferring data packets between said data packet storage means and said control means;

a packet number queue for storing a plurality packet numbers, each said packet number stored in said packet number queue being accessible by said processor and said control means; and

packet number transfer means for transferring said packet numbers from said packet number queue and at least one of said control means and said processor, and for transferring packet numbers from said memory management means to at least one of said control unit and said processor.

26. The data communication controller of claim 25, wherein said packet number queue has a plurality of storage locations including a first insert storage location at which each said packet number is inserted into said packet number queue, and a first removal storage location from which said each packet number is removed from said packet number queue.

27. The data communication controller of claim 26, wherein said memory management means comprises

data page determining means for determining the number of data page storage locations required for storing each said data packet,

data page allocating means for dynamically allocating said required number of free data page storage locations to said data packet, and

packet number assigning means for dynamically assigning the corresponding packet number to each said allocated free data page storage locations.

28. The data communication controller of claim 26, wherein each said set of physical addresses specifies at least one byte of memory for storage of status data regarding each said corresponding data packet, and wherein said data packet transfer means can selectively transfer said status data (i) from said control means to said at least one byte of memory storage, and (ii) from said at least one byte of memory storage, to said processor.

29. The data communication controller of claim 25, wherein there is a fixed address increment between each consecutive pair of address values.

30. The data communication controller of claim 25, wherein a first predetermined number of the most significant bits of said set of linear address bits represent a page of packet data for storage in one said data packet page location of said data packet storage means, and wherein a second predetermined number of the least significant bits of said set of linear address bits represent the range of data bytes contained in each said page of packet data for storage in each said data packet page of said data packet storage means.

31. The data communication controller of claim 25, wherein said packet number queue comprises a FIFO storage device.

32. The data communication controller of claim 25, wherein said memory management means further comprises

data page allocating means for dynamically allocating one or more free data page storage locations in said data packet storage means, for storage of each said data packet, and

packet number assigning means for dynamically assigning said corresponding packet number to said one or more allocated free data page storage locations.

33. The data communication controller of claim 27, wherein said memory management means further comprises

releasing means operably associated with said data page allocating means for releasing data page storage locations allocated to corresponding packet number, in response to a release request made in communication with said corresponding packet number.

34. The data communication controller of claim 27, wherein said data page determining means is responsive to an initial page request and to one or more additional page requests, as incoming data associated with a receive data packet is being received.

38. The data communication controller of claim 25, wherein said memory management means comprises

data page determining means for determining the number of data page storage locations required to store each said data packet;

data page allocating means for dynamically allocating said required number of free data page storage locations to said data packet, and

packet number assigning means for dynamically assigning the corresponding packet number to said allocated free data page storage locations.

44. The data communication controller of claim 38, wherein said memory management means further comprises

releasing means operably associated with said data page allocating means for releasing data pages allocated to the corresponding packet number, in response to a release request made in connection with said corresponding packet number.

45. The data communication controller of claim 38, wherein said data page determining means is responsive to an initial page request and to one or more additional page requests, as incoming data associated with a receive data packet is being received.

35. A data communication controller for interfacing with a processor and operably associating with a data packet storage means having a plurality of data page storage locations for storing one or more transmit data packets and one or more receive data packets, said data communication controller comprising;

control unit for accessing a communication medium;

memory management means for managing said data packet storage means independent of said processor by assigning a packet number to each said transmit data packet and each receive data packet to be stored in said data packet storage means and allocating one or more data page storage locations for each said transmit data packet and said receive data packet to be stored;

linear address bit receiving means for receiving one or more sets of linear address bits from said processor or said control means, each said set of linear address bits received from said processor corresponding to one said transmit data packet and ranging from a minimum address value to a maximum address value, and each said set of linear address bits received rom said control unit corresponding to one said receiving data packet and ranging from a minimum address value to a maximum address value;

physical address generating means for generating a set of physical addresses for each data packet to be stored in said data packet storage means, by using the data packet number assigned to said corresponding data packet to be stored and said set of linear address bits corresponding to said data packet to be stored, each said set of physical addresses corresponding to one or more data page storage locations and providing access to said one or more data page storage locations;

data packet transfer means for transferring one or more said transmit data packets between said processor and said data packet storage means and between said data packet storage means and said control means, and for transferring one or more said receive data packets between said control means and said data packet storage means and from between said data packet storage means and said processor;

transmit packet number queue for storing one or more packet numbers, each said packet number stored in said transmit packet number queue corresponding to one said transmit data packet stored in said data packet storage means;

receive packet number queue for storing one or more packet numbers, each said packet number stored in said receive packet number queue corresponding to one said receive data packet stored in said data packet storage means; and

packet number transfer means for transferring packet numbers from said memory management unit to said processor, for transferring packet numbers from said transmit packet number queue to said control means, for transferring packet numbers from said memory management to said control means, and for transferring packet numbers from said receive packet number queue to said processor.

36. The data communication controller of claim 35, wherein said transmit packet number queue has a plurality of storage locations including a first insert storage location at which each said packet number is inserted into said transmit packet number queue, and a first removal storage location from which each said packet number is removed from said transmit packet number queue, and wherein said receive packet number queue has a plurality of storage locations including a second insert storage location at which each said packet number is inserted into said receive packet number queue, and a second removal storage location from which each said packet number is removed from said receive packet number queue.

37. The data communication controller of claim 36, wherein said transmit packet number queue comprises a first FIFO storage device and said receive packet number queue comprises a second FIFO storage device.

39. The data communication controller of claim 35, wherein each said set of physical addresses specifies at least one byte of memory for storage of status data regarding each said corresponding data packet, and wherein said data packet transfer means can selectively transfer said status data (i) from said control means to said at least one byte of memory storage, and (ii) from said at least one byte of memory storage, to said processor.

40. The data communication controller of claim 35, wherein there is a fixed address increment between each consecutive pair of address values.

41. The data communication controller of claim 35, wherein a first predetermined number of the most significant bits of said set of linear address bits represent a page of packet data for storage in one said data packet page location of said data packet storage means, and wherein a second predetermined number of the least significant bits of said set of linear address bits represent the range of data bytes contained in each said page of packet data for storage in each said one data packet page of said data packet storage means.

42. The data communication controller of claim 35, wherein said packet number queue comprises a FIFO storage device.

43. The data communication controller of claim 35, wherein said memory management means further comprises

data page allocating means for dynamically allocating one or more free data page storage locations in said data packet storage means, for storage of each said data packet, and

packet number assigning means for dynamically assigning said corresponding packet number to said one or more allocated free data page storage locations.