Communications highway network system

• US 5,471,474 A
• Filed: 06/04/1993
• Issued: 11/28/1995
• Est. Priority Date: 06/04/1993
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: LANcity Corporation (Nortel Networks Corporation)
• Inventors: Grobicki, Christopher, Mazza, Cynthia, O'Connell, Edward, Ulm, John, White, Gerard
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): TON, DANG T
• Application Number:
  US08/072,585
• Time in Patent Office: 907 Days
• Field of Search: 370/85.2, 370/85.3, 370/60, 370/94.1, 370/85.6, 370/85.7, 370/85.1, 370/108, 370/85.9, 370/85.4, 370/85.5, 370/105.1, 370/100.1, 370/95.1, 370/95.3, 340/825.5, 340/825.51, 340/825.52, 340/825.05, 455/6.1, 455/6.2, 455/6.3, 455/13.3, 455/82, 375/354, 375/365
• US Class Current: 370/437
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04N 7/173 with two-way working, e.g. subscriber sending a programme selection signal

Abstract

A communications highway network system for the interactive communication of digital and analog information that incorporates LAN, MAN, and CATV technology to provide an information pathway of metropolitan size that has a spanning tree topology. The system is multiple drop that operates according a network protocol. The network protocol is based on modified TDM techniques, compensation for round trip loop delay, dynamic allocation of time slots on the network bus, and global synchronization. The protocol also permits concatenation of data packets to reduce overhead. Access to the network bus is controlled by a system allocator operating according to the network protocol. The allocator may allocate network bus bandwidth to simultaneously provide three levels of service for the system nodes to access the network bus, namely, isochronous, demand-based dedicated, and contention bandwidth allocation. This allocation method incorporates fairness to give all nodes sufficient bus access opportunities.

Claims

1. A communications network for interactive communications among network users, comprising:

a network bus;

a plurality of system nodes connected to the network bus with each system node having a loop delay associated therewith;

a pacer connected to the network bus for providing timing signals thereon for synchronizing network bus access operations by the plurality of system nodes;

an allocator that is capable of substantially simultaneously allocating the plurality of system nodes access to a network bus bandwidth by a plurality of bus allocation methods according to a network bus protocol that is based on the network bus being segmented in a time domain into repeating periods, compensation by each system node of its loop delay before accessing the network bus to transmit data during a repeating period, dynamically allocating access to the network bus bandwidth according to the plurality of bus allocation methods, and timing signals from the pacer, with at least one of the bus allocation methods being based on system nodes accessing the network bus bandwidth according to this method being given a requested discrete portion of network bus bandwidth for a predetermined number of repeating periods for transmitting data on the network bus.

2. The communications network as recited in claim 1, wherein the network bus further includes buses of systems that connect to the system nodes.

3. The communications network as recited in claim 1, wherein the plurality of bus allocation methods includes isochronous, demand-based dedicated, and contention allocation methods.

4. The communications network as recited in claim 3, wherein the isochronous method of network bus bandwidth allocation is based on system nodes accessing discrete portions of the network bus bandwidth for a predetermined number of repeating periods for the transmission of data.

5. The communications network as recited in claim 3, wherein the allocator in response to requests from a plurality of the system nodes allocates to such system nodes access to the network bus bandwidth according to demand-based dedicated and contention allocation methods.

6. The communications network as recited in claim 5, wherein the allocator allocates system nodes access to discrete portions of the network bus bandwidth according to the demand-based dedicated allocation method for one repeating period.

42. The communications network as recited in claim 1, wherein one of the plurality of system nodes is the pacer.

43. The communications network as recited in claim 42, wherein the pacer further includes the allocator.

44. The communications network as recited in claim 3, wherein the allocator in response to requests from a plurality of the system nodes allocates to such system nodes access to the network bus bandwidth according to demand-based dedicated and contention allocation methods based on an amount of data being transmitted on the network bus.

45. The communications network as recited in claim 3, wherein the allocator in response to requests from a plurality of the system nodes allocates to such system nodes access to the network bus bandwidth according to demand-based dedicated and contention allocation methods based on a number of collisions of data occurring on the network bus.

7. A method for accessing a network bus bandwidth, comprising the steps of:

(A) generating timing signals on the network bus for synchronizing network bus access operations by a plurality of system nodes connected to the network bus;

(B) segmenting the network bus in a time domain into a plurality of repeating time periods;

(C) determining for each system node that system node'"'"'s loop delay;

(D) each system node that seeks access to the network bus bandwidth according to a first network bus access method transmitting a request to an allocator for assignment of a discrete portion of the network bus bandwidth for a predetermined number of repeating periods in which the requesting system nodes may transmit data packets on the network;

(E) the allocator assigning the system nodes that requested assignment of a discrete portion of the network bandwidth at step (D) a discrete portion of the network bus bandwidth for a predetermined number of repeating periods until a total amount of network bus bandwidth assigned by the allocator equals a predetermined maximum bandwidth, and for any system nodes that the allocator rejects its request for access according to this first network bus access method because the predetermined maximum bandwidth is reached, then step (G);

(F) the system nodes assigned discrete portions of network bus bandwidth at step (E) transmitting data packets onto the network bus at a time up to an amount assigned by the allocator, with each of such system nodes commencing transmission of the data packets one loop delay before a time the allocator assigned for that system node for transmitting data packets on the network bus;

(G) continuously monitoring an amount of data packets on the network bus and a number of collisions of data packets on the network bus;

(H) allowing any of the plurality of system nodes to transmit at least one data packet on the network bus by a second network bus access method, with each of such system nodes using the second network bus access method commencing transmission of the at least one data packet one loop delay before a time block the allocator has assigned for such system nodes to transmit on the network bus and at least one deferral condition is met;

(I) the allocator accepting requests from any of the plurality of system nodes for discrete portions of a next repeating period to transmit at least one data packet on the network bus according to a third network bus access method; and

(J) the allocator assigning a discrete portion of the network bus bandwidth of the next repeating period to each up to a predetermined number of the system nodes requesting access at step (I) to the network bus according to the third network bus access method, with each of such system nodes accessing this network bus according to the third network bus access method commencing transmission of the at least one data packet one loop delay before a time the allocator has assigned for each system node to transmit on the network bus.

8. The method as recited in claim 7, wherein step (A) globally synchronizes operations on the network bus.

9. The method as recited in claim 7, wherein step (C) includes the following substeps:

(1) a system node transmitting at least one data packet to itself on the network bus;

(2) starting a timing means upon a start of the transmission at substep (1) of step (C);

(3) receiving back at the system node the data packet transmitted at substep (1) of step (C);

(4) stopping the timing means upon receiving back the data packet at substep (3) of step (C) and calculating the loop delay based on the start and stop times; and

(5) storing at the system node the loop delay calculated at substep (4) of step (C).

10. The method as recited in claim 7, wherein the allocator is capable of substantially simultaneously assigning the first, second, and third network bus access methods to the plurality of system nodes.

11. The method as recited in claim 7, wherein steps (H), (I), and (J) result in a dynamic assignment of network bus bandwidth according to the second and third network bus access methods based on a load of each of the nodes on the network bus.

12. The method as recited in claim 11, wherein a number of system nodes requesting access to the network bus bandwidth according to the third network bus access method increases as a number of collisions of data packets on the network bus increases.

13. The method as recited in claim 11, wherein a number of system nodes requesting access to the network bus bandwidth according to the third network bus access method increases as the number of data packets on the network bus increases.

14. The method as recited in claim 12, wherein the allocator in assigning a portion of the network bus bandwidth to the system nodes requesting access to the network bus bandwidth according to the third network bus access method will assign a discrete portion of the network bus bandwidth to each requesting system node until a total amount of network bus bandwidth assigned is equal to a predetermined maximum bandwidth and queuing any requests for access to the network bus bandwidth according to the third network bus access method that were rejected because the predetermined maximum bandwidth was reached.

15. The method as recited in claim 14, wherein the queued requests have priority in an assignment of discrete portions of the network bus bandwidth in subsequent repeating periods for access to the network bus according to the third network bus access method.

16. The method as recited in claim 7, wherein transmitting data packets onto the network bus according to the first, second, and third network bus access methods includes transmitting a data frame, with the data frame having a plurality of data packets, the data frame having less at least network bus bandwidth overhead than if the plurality of data packets making up the data frame are transmitted separately.

17. The method as recited in claim 16, wherein transmitting the data frame onto the network bus according to the second network bus access method includes transmitting a first data packet of the data frame according to the second network bus access method and a remainder of the data packets that follow the first data packet according to a dedicated bus access method.

30. The method as recited in claim 7, wherein the method further includes increasing a probability of collision detection by ensuring that collisions for a particular data packet occur before a predetermined time after a start of transmission of that data packet.

32. The method as recited in claim 7, wherein each data packet to be transmitted includes at least one field for permitting additional information to be carried by that data packet.

34. The method as recited in claim 7, wherein each system node is capable of transmitting data packets onto the network bus according to the second network bus access method when a remaining length of a data frame presently on the network bus is less than that system node'"'"'s loop delay.

36. The method as recited in claim 7, wherein each system node includes a means that the allocator accesses to provide transmit information for that system node on a per time slot basis.

37. The method as recited in claim 36, wherein the means that the allocator accesses includes a transmit opportunity table.

40. The method as recited in claim 16, wherein each data packet of the data frame has its own source address and destination address.

18. A method for accessing a network bus bandwidth, comprising the steps of:

(A) generating timing signals on the network bus for synchronizing network bus access operations by a plurality of system nodes connected to the network bus;

(B) determining for each system node that system node'"'"'s loop delay;

(C) segmenting the network bus in the time domain into repeating periods of predetermined length and dividing each of the repeating periods into a plurality of time slots, with each repeating period including a predetermined number of time slots for transmission of a timing signal generated at step (A), a predetermined number of time slots for system nodes to transmit data packets on the network bus based on the system nodes accessing the network bus according to a first network bus access method, a predetermined number of time slots for system nodes to transmit data packets on the network bus based on the system nodes accessing the network bus according to a second network bus access method, and a predetermined number of time slots for system nodes to transmit data packets on the network bus based on the system nodes accessing the network bus according to a third network bus access method;

(D) each system node seeking access to the network bus bandwidth according to the first network bus access method transmitting a request to an allocator for assignment of a discrete portion of the network bus bandwidth defined by the predetermined time slots set forth in step (C) for system nodes to access the network bus according to the first network bus access method;

(E) the allocator assigning each of the system nodes requesting a portion of the network bus bandwidth at step (D) a discrete portion of the network bus bandwidth until a total amount of network bus bandwidth assigned by the allocator equals the predetermined number of time slots set forth in step (C) for system nodes to access the network bus according to the first network bus access method, and for any system nodes that the allocator rejects its request for a discrete portion of the network bus bandwidth requested at step (D), then step (G);

(F) the system nodes assigned network bus bandwidth at step (E) transmitting data packets onto the network bus at a time up to an amount assigned by the allocator, with each of the system nodes commencing transmission of the data packets one loop delay before the time the allocator assigned for each system node to transmit on the network bus;

(G) continuously monitoring an amount of data packets on the network bus and a number of collisions of data packets on the network bus;

(H) allowing any of the plurality of system nodes to transmit at least one data packet on the network bus by the second network bus access method in the predetermined number of time slots set forth in step (C) for system nodes accessing the network bus according to the second network bus access method, with each of the system nodes using the second network bus access method commencing transmission of the at least one data packet one loop delay before the predetermined number of time slots set forth at step (C) for system nodes accessing the network bus according to the second network bus access method and at least one deferral condition is met;

(I) the allocator accepting requests from any of the plurality of system nodes for discrete portions of a next repeating period of the predetermined number of time slots set forth in step (C) for system nodes accessing the network bus according to the third network bus access method; and

(J) the allocator assigning discrete portions of the next repeating period of the predetermined number of time slots set forth in step (C) for system nodes accessing the network bus according to the third network bus access method according to the requests at step (I), with each of such system nodes using the third network bus access method commencing transmission of at least one data packet one loop delay before a time the allocator has assigned for such system nodes to transmit data packets onto the network bus.

19. The method as recited in claim 18, wherein step (A) globally synchronizes operations on the network bus.

20. The method as recited in claim 18, wherein step (B) includes the following substeps:

(1) a system node transmitting at least one data packet to itself on the network bus;

(2) starting a timing means at a start of the transmission at substep (1) of step (B);

(3) receiving back at the system node the data packet transmitted at substep (1) of step (B);

(4) stopping the timing means upon receiving back the data packet at substep (3) of step (B) and calculating the loop delay based on the start and stop times; and

(5) storing at the system node the loop delay calculated at substep (4) of step (B).

21. The method as recited in claim 18, wherein the allocator is capable of substantially simultaneously assigning the first, second, and third network bus access methods to the plurality of system nodes.

22. The method as recited in claim 18, wherein steps (H), (I), and (J) result in a dynamic assignment of network bus bandwidth according to the second and third network bus access methods based on a load of each of the nodes on the network bus.

23. The method as recited in claim 22, wherein a number of system nodes requesting access to the network bus bandwidth according to the third network bus access method increases as a number of collisions of data packets on the network bus increases.

24. The method as recited in claim 22, wherein a number of system nodes requesting access to the network bus bandwidth according to the third network bus access method increases as a number of data packets on the network bus increases.

25. The method as recited in claim 23, wherein at step (J) the allocator assigns each of the system nodes requesting a portion of the network bus bandwidth a discrete portion of the network bus bandwidth until a total amount of the network bus bandwidth assigned equals the predetermined number of time slots set forth in step (C) for system nodes accessing the network bus according to the third network bus access method, and queuing the requests for discrete portions of the network bus bandwidth that were rejected because the total predetermined number of time slots set forth in step (C) has been reached for system nodes accessing the network bus according to the third access method.

26. The method as recited in claim 25, wherein the allocator assigns for the requests in the queue a discrete number of time slots of subsequent repeating periods having a predetermined number of time slots as set forth in step (C) for system nodes accessing the network bus according to the third network bus access method.

27. The method as recited in claim 25, wherein for subsequent repeating periods the requests in the queue are given priority for the assignment of the predetermined number of time slots set forth in step (C) for system nodes accessing the network bus according to the third network bus access method.

28. The method as recited in claim 18, wherein transmitting data packets onto the network bus according to the first, second, and third network bus access methods includes transmitting a data frame, with the data frame having a plurality of data packets, the data frame having less at least network bus bandwidth overhead than if the plurality of data packets making up the data frame are transmitted separately.

29. The method as recited in claim 28, wherein transmitting the data frame onto the network bus according to the second network bus access method includes transmitting a first data packet of the data frame according to the second network bus bandwidth access method and a remainder of the data packets that follow the first data packet according to the a dedicated bus access method.

31. The method as recited in claim 18, wherein the method further includes increasing a probability of collision detection by ensuring that collisions for a particular data packet occur before a predetermined time after a start of transmission of that data packet.

33. The method as recited in claim 18, wherein each data packet to be transmitted includes at least one field for permitting additional information to be carried by that data packet.

35. The method as recited in claim 18, wherein each system node is capable of transmitting data packets onto the network bus according to the second network bus access method when a remaining length of a data frame presently on the network bus is less than that system node'"'"'s loop delay.

38. The method as recited in claim 18, wherein each system node includes a means that the allocator accesses to provide transmit information for that system node on a per time slot basis.

39. The method as recited in claim 38, wherein the means that the allocator accesses includes a transmit opportunity table.

41. The method as recited in claim 28, wherein each data packet of the data frame has its own source address and destination address.

46. A method for allocating access to a network bus of a communications network having a plurality of system nodes, comprising the steps of:

segmenting a network bus bandwidth in a time domain into repeating periods;

partitioning each of the repeating periods of the network bus bandwidth into a predetermined amount of network bus bandwidth for each of a plurality of bus allocation methods;

dynamically allocating access by the system nodes to the network bus bandwidth according to the plurality of bus allocation methods, with the allocation of access by the system nodes to the network bus bandwidth according to a first bus allocation method including the steps of,

accepting requests from each system node seeking access to the network bus bandwidth according to the first bus allocation method for discrete portions of the network bus bandwidth, and

assigning to each of the system nodes that requested access to the network bus bandwidth according to the first bus allocation method a discrete portion of the network bus bandwidth until a total amount of the network bus bandwidth assigned equals the predetermined amount of network bus bandwidth partitioned for the first allocation method; and

transmitting a transmit map update packet to the plurality of system nodes to control access to the network bus by the plurality of system nodes.

47. The method as recited in claim 46, wherein the first bus allocation method is an isochronous allocation method.

48. The method as recited in claim 46, wherein allocating access by the system nodes to the network bus bandwidth according to a second bus allocation method comprises:

monitoring an amount of data packets on the network bus and a number of collisions of data packets on the network bus; and

allowing any of the plurality of system nodes to transmit at least one data packet on the network bus by a second bus allocation method as long as at least one deferral condition is met.

49. The method as recited in claim 48, wherein the second bus allocation method is a contention allocation method.

50. The method as recited in claim 48, wherein allocating access by the system nodes to the network bus bandwidth according to a third bus allocation method comprises:

accepting requests from any of the plurality of system nodes for discrete portions of a next repeating period of the network bus bandwidth;

assigning discrete portions of the next repeating period of the network bus bandwidth according to the requests for such portions, until a total amount of the network bus bandwidth assigned equals an amount of the network bus bandwidth available; and

queuing any of the requests that were not assigned discrete portions of the next repeating period of the network bus bandwidth.

51. The method as recited in claim 50, wherein the third bus allocation method is a demand-based dedicated allocation method.

52. The method as recited in claim 50, further comprising, for subsequent repeating periods, giving priority for the assignment of the predetermined amount of network bus bandwidth partitioned for the third of the bus allocation methods to the queued requests.

53. A method for accessing a network bus bandwidth, comprising the steps of:

segmenting the network bus in a time domain into a plurality of repeating periods and dividing each of the repeating periods into a plurality of time slots;

allocating a first predetermined number of the plurality of time slots for use by system nodes to transmit data packets on the network bus according to a first network bus allocation method if requested;

allocating a remainder of the plurality of time slots for use by system nodes to transmit data packets on the network bus according to a second network bus allocation method;

assigning discrete portions of the first predetermined number of the plurality of time slots for system nodes to transmit data packets on the network bus according to the first network bus allocation method according to a dedicated bandwidth allocation method; and

permitting system nodes to transmit data packets on the network bus according to the second network bus allocation method according to a contention allocation method.

54. A method for accessing a network bus bandwidth, comprising the steps of:

generating timing signals on the network bus for synchronizing network bus access operations by a plurality of system nodes connected to the network bus;

segmenting the network bus in a time domain into a plurality of repeating time periods and dividing each of the repeating time periods into a plurality of time slots;

allocating a first predetermined number of the plurality of time slots for use by system nodes to transmit data packets on the network bus according to a first network bus allocation method if requested;

allocating a remainder of the plurality of time slots for use by system nodes to transmit data packets on the network bus according to a second network bus allocation method after allocating time slots for the first and a third network bus allocation methods;

allocating a third predetermined number of the plurality of time slots for use by system nodes to transmit data packets on the network bus according to the third network bus allocation method if requested;

assigning discrete portions of the first predetermined number of the plurality of time slots for system nodes requesting access to the network bus to transmit data packets according to the first network bus allocation method;

permitting system nodes to transmit data packets on the network bus according to the second network bus allocation method; and

assigning discrete portions of the third predetermined number of the plurality of time slots of the next repeating period for system nodes requesting access to the network bus according to the third network bus allocation method.

55. The method as recited in claim 54, wherein the first network bus allocation method is an isochronous allocation method, the second network bus allocation method is a contention allocation method, and the third network bus allocation method is a demand-based dedicated allocation method.