Time slotted logical ring

A Time Slotted Logical Ring protocol manages the flow of traffic in a duplex media including a cable distribution network with a head end, a local node, and a group of subscribers. The subscriber includes a cable modem which produces an HDLC serial interface which then goes to the subscriber or gets converted to ethernet by a router and then to the subscriber. The Time Slot portion of TSLR protocol manages upstream and downstream access and uses time tick identification frames in the downstream direction to control upstream traffic. A multiple logical ring protocol in TSLR is used to allocate cable bandwidth between the multiple subscribers.

A cable modem network includes a head end located at a cable company central location. The head end distributes cable services to different local areas of subscribers. Subscriber stations are terminated by cable modem boxes that are connected to the subscriber's computer through a conventional data interface such as serial or Ethernet. The cable modem boxes allow the subscribers to transmit data back upstream on the cable network to the head end. For example, if a subscriber wishes to order a pay-for-view movie, the subscriber enters a selection that is transmitted by the cable modem back over the cable network to the head end. The head end then transmits a downstream signal to the subscriber with the selected movie.

With the installation of more subscribers on cable modem networks, it becomes more important to allocate bandwidth more efficiently on the cable return path. For example, different types of transmissions, such as voice traffic may require a higher priority than data traffic. Alternatively, certain subscribers may need to purchase more bandwidth or higher priority than other subscribers. Current cable modem systems do not efficiently allocate cable bandwidth over the return path.

Accordingly, a need remains for a cable access system that allows multiple users to both send and receive information in an orderly and efficient manner.

SUMMARY OF THE INVENTION

Communications between a head end and multiple subscribers on a cable network are scheduled using a Time Slotted Logical Ring protocol (TSLR). Data is broadcast from the head end to the subscribers over a downstream path of a broadcast media, such as a combination of a fiber optical link and coaxial cable. The TSLR protocol allocates bandwidth to subscribers on an upstream path of the broadcast media by assigning the subscribers to time slots on different logical ring levels. The time slots on a first ring level represent the total available bandwidth for the upstream path. The portion of the bandwidth allocated to one or more of the time slots on the first ring level are distributed between multiple time slots on lower ring levels that represent different user bandwidth requirements.

The TSLR protocol rotates selection of the time slots around the first ring level allowing the subscriber assigned to the selected time slot to transmit data upstream to the head end. When the selected time slot opportunity on the first ring level is allocated to a lower ring level, the TSLR protocol allows the subscriber assigned to the selected time slot on the lower ring level to transmit. The TSLR protocol then rotates assignment of another time slot on the lower ring level to the time slot on the first ring. Thus, each subsequently lower TSLR ring level allocates relatively smaller portions of upstream bandwidth to the subscribers.

The head end sends time tick identifier (TTI) frames to the subscribers assigned to the currently selected time slots. The TTI frames are used to notify the identified subscriber to transmit frames upstream back to the head end. After receiving the TTI frame, the subscriber sends back either a data frame or a heart beat frame to the head end. The heart beat frame is sent when the subscriber has no data to transmit or when transmitting a reduced sized data frame. The heartbeat frame is used by the head end to assign the subscriber to different ring levels. For example, subscribers sending only heartbeat frames back to the head end for a specified time period are assigned to lower frame levels than subscribers sending back data frames.

The subscribers are assigned to different ring levels and, in turn, sent TTI frames at different rates according to different scheduling criteria. In one embodiment of the invention as mentioned above, the subscribers are assigned to different ring levels according to the number of data frames sent back from the subscribers to the head end within specified time periods. The subscribers can also be assigned to classes. The TSLR then meters out a maximum number of TTI frames to individual subscribers within a fixed time period according to the assigned subscriber classes. The subscribers can also be allocated time-bandwidth credits. The credits allocated to each subscriber are reduced upon receiving TTI frames and TTI frames are no longer sent to subscribers with zero credits. The credits for the subscribers are then increased after selected time intervals.

Bandwidth efficiency is improved by releasing early TTI frames after the head end receives a subscriber heart beat frame. Efficiency is also improved by aggregating multiple subscriber data frames together and sending the aggregated frames all at one time to the head end. To prevent allocating too much bandwidth to low bit rate subscribers, the highest ring level assigned to individual subscribers is controlled according to a maximum transmission rate of the individual subscribers.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a cable modem network12. A broadcast media includes links24and26and exists in both a downstream direction14and an upstream direction16. A head end18includes a computer data manager located at a cable company central location. In newer cable installations, the head end18connects first to a local node20over a long haul fiber optic link24. The local node20then converts from the fiber optic link24to a coaxial cable26and distributes cable services to a local area28of subscribers22.

In a dense residential area, the local node20might have 2 to 4 main coaxial cable (coax) runs26that support a total of 300 to 500 subscribers22(homes) within a 1 to 2 mile radius. Less dense areas have less homes and a larger radius. The long haul link24is typically between 0 to 13 miles. The head end18typically supports40local nodes20. Each local node20has its own unique upstream path16. Older cable wiring plants do not have local nodes20and drive main cable runs directly from the head end18.

Referring toFIG. 2, the head end18connects to a local computer server or through a router38to the Internet or an internal data network known as an intranet40. The subscribers22each include a cable modem box42connected to a computer52through a conventional data interface such as serial or Ethernet50. At a home or small office/home office (SOHO), the personal computers (PCs)52are connected together so they can share the same high speed Internet service. A router or bridging/switching circuit48is commonly used to convert from Ethernet local area network (LAN)50to serial wide area network54. On the analog side, RF modulators32and44provide the forward path14(downstream) and the return path16(upstream) between the head end18and the SOHO over the shared broadcast media24,26. On their digital side, the RF modulators32and44provide a standard synchronous serial interface that consists of bidirectional clock and data streams.

The head end18includes the central router38that connects to the local intranet, or out to a public internet40through a WAN connection39such as frame relay or asynchronous transfer mode (ATM). Data packets between the central router38and the subscriber's router48are placed in frames and transferred over the shared coax media24,26. The cable plant between the head end18and the subscriber location22is too large for a carrier sense multiple access/collision detect (CSMA-CD) Ethernet like protocol to run efficiently. Therefore, Ethernet is used only as a local data interface at the head end18and at the subscribers22.

An access and scheduling protocol known as Time Slotted Logical Ring (TSLR) is employed internal to the cable modem network12between the head end18and the subscribers22. TSLR coordinates and ensures timely delivery of downstream and upstream traffic, prioritizes traffic, reallocates bandwidth for bursting, and efficiently shares access for all subscriber nodes. TSLR operates independently of data protocols like Ethernet or TCP/IP that TSLR transfers. A TSLR based system can, therefore, be expanded to support user interfaces other than ethernet, such as integrated services digital network (ISDN) for voice, or even ATM for mixed media.

An open system interconnection (OSI) layer1physical layer (PHY) consists of the RF modems32and34that provide a bidirectional media between the head end18to the cable modem22. The PHY layer operates independently of the TSLR protocol. An OSI layer2media access control (MAC) layer is TSLR and consists of two parts. The first part is TSLR framing, and the second part is TSLR link management. An OSI layer3network layer is independent of TSLR and typically is internet protocol (IP) or point-to-point protocol (PPP). Layer3can also be an encapsulated Ethernet or ATM cells. An OSI layer4transport protocol is independent of TSLR and is typically transmission control protocol (TCP).

Data is managed in both the upstream and downstream directions. In both directions, there are several arbitration operations performed by the TSLR.

Access: Contention is resolved between multiple subscribers22who wish to gain access to the upstream bandwidth. A “Time Slot” portion of TSLR resolves contentions by performing all accesses at predetermined intervals that are coordinated by the head end18.

Bandwidth Management: Bandwidth is managed so that subscribers22get faster response time and larger bandwidth usage upon demand. The “logical ring” portion of the TSLR manages bandwidth by classifying subscribers according to their traffic patterns, and gives heavy traffic subscribers faster access time, higher bandwidth, and hence lower latency.

The head end18manages all the access mechanisms for the Time Slotted Logical Ring. The local node20does not control access. However, all delay calculations are done with respect to the local area network28between the local node26and the subscribers22(FIG. 1). The head end18remotely manages the local network28of subscribers22that exist within the physical local node20.

For upstream access16, there is one homogenous media with one receiver and many potential transmitters. If more than one subscriber22transmits at a time, there will be a data collision, and data will be lost. The TSLR conducts deterministic access control to prevent collisions. The TSLR partitions bandwidth to all subscribers22to allow universal access, but can partition the majority of the bandwidth to one or more subscribers22who may be bursting large amounts of data for a short period of time. The TSLR dynamically adjusts the bandwidth allotment to different subscribers.

Referring toFIG. 3, upstream bandwidth is divided up between all subscribers22. As much bandwidth is made available as possible to any one subscriber22if no one else is using it, and access time to busy subscribers is minimized to keep the network latency low. To achieve this objective, the TSLR protocol classifies all subscribers22into a series of levels based upon their level of recent activity. Level0provides a constant bit rate. Level1is the highest level for multiple levels that have a variable bit rate.

A very basic TSLR protocol has only two ring levels56and58: active and inactive. Active subscribers22are users who have transmitted data within a recent time period and are assigned time slots62on a first ring level56. Any subscriber22who is not active is therefore inactive and is assigned a time slot64on a second ring level58. The length of time that defines recent is known as the aging time and is a TSLR configuration parameter. The number of frames sent by a subscriber within the aging time (excluding heart beat frames) to qualify for active status is known as the aging frames and is a TSLR configuration parameter.

In one example, the level1aging parameter is one frame within a time period as small as 20 milliseconds, or as long as 30 minutes. In this example, the list of active subscribers62are placed on the level1TSLR56. The inactive subscribers22are placed on the level2TSLR58. The head end18sends a time tick identifier frame (TTI) notifying the subscriber it is now allowed to transmit. The TTI's are sent out to each subscriber22in level1in a logical sequence. If there were four current subscribers22assigned to the level1ring56, each subscriber22receives permission to transmit every fourth time slot, effectively giving each subscriber22one quarter of the upstream bandwidth. The level2TSLR ring58has one or more of its subscribers receives permission to transmit once every rotation through the level1TSLR56. The level2TSLR subscribers22, as a group, shares one or more time slots62A in the level1TSLR ring56.

The number of subscribers from the level2TSLR ring58that are granted permission to transmit per rotation of the level1TSLR ring56is designated by a network configuration parameter, and is a percentage value known as lower ring access interval (LRAI). For example, say the LRAI for level1was 25%. Then one level2TTI is issued after every three level1TTI's. 75% of the network bandwidth is available to current and busy subscribers62on level1, while 25% of the network bandwidth is shared by new subscribers62or by low bandwidth subscribers62assigned to level2.

If there is only one subscriber in level1, the one subscriber22receives three TTI's in a row. This optimizes the amount of bandwidth available to the subscriber22in a given burst interval. However, care is taken so that bandwidth is not lost. If the local cable television (CATV) upstream bandwidth (for example 10 million bits per second (Mbps) is greater than the interface bandwidth (for example 1 Mbps) of the subscriber22, then the subscriber22is not issued subsequent TTI's since the TTI's could not be used. TTI Metering explained below prevents assigning too much bandwidth to individual subscribers22.

At a more advanced level, the TSLR protocol runs more efficiently with more than 2 levels of TSLR rings.FIG. 3also illustrates a third TSLR ring60having one of multiple time slots66assigned to slot64A in TSLR ring58. Note that only the head end18is aware of the scheduling constraints and level assignments. The subscribers22react only after receiving a TTI, and have no concept of ring levels. Thus, the head end18scheduling software may be updated or changed without changing software in the subscribers.

TSLR Applied to Constant Bit Rate Traffic

An example of constant bit rate traffic is voice. Voice traffic is generated and received at a rate of 8,000 bytes per second (Bps). Voice is typically sent over a shared media one byte at a time using a time slot mechanism. To transport voice over TSLR, the voice samples are gathered into small frames or cells. Doing this adds latency into the voice path, so cell sizes are kept as small as possible. For example, 48 bytes of voice is collected and then forwarded. At 8 kBps, the net latency added is: 48 bytes/8,000 bytes/sec=6 milliseconds. Once the voice is in a frame form, it is passed through the network in an asynchronous manner. However, the short frame size is wasteful on network bandwidth.

This inefficiency is solved by introducing a logical ring55at level0. Only cell traffic57is allowed on ring level0. As such, TTI's are very closely spaced and bandwidth is preserved. Ring level0is initiated and sequenced once every 6 milliseconds and preempts the level1through level3rings. The net effect is that level0becomes a synchronous ring and levels1through3become asynchronous rings. TTI early release and packet aggregation are not needed on the level0ring because all the frames are at their maximum frame size (for example, 48 bytes+overhead). Near 100% bandwidth efficiency is achieved.

Signaling frames for voice call set-up and tear-down is accommodated on either ring structure. If the voice signaling is contained in time division multiplexed (TDM) frames within the equipment connected at either external ends of the TSLR network, then the signaling information is embedded into the level0ring. If the signaling is frame based and originates from within the TSLR environment, the signaling frames are sent over the lower asynchronous rings.

Asynchronous transfer mode (ATM) converts all information into 53 bytes cells. ATM is handled in the same manner described above for voice. On a pure ATM network, the MTU for all the cable modems is set to 53 bytes and TTI frames are released based upon this frame length for all TSLR rings. As a result, frames appear back-to-back with very little wasted bandwidth.

Note that for both ATM and voice, the frame size is small and the time between time ticks is also small. The frame aggregation and early TTI release algorithms are not needed in this case. The level0ring runs efficiently because the head end18issues a sequence of TTI's without waiting for anything back from the subscribers22, essentially pipe-lining the TTI's. The only network delay that must be accommodated is the delay within the local node tree structure26. In effect, the head end18is remotely managing a local network.

An example of a 5 level TSLR scheduler is shown inFIG. 4. A TTI is transmitted to the subscriber22assigned to the next time slot in ring #1in step92. When the current time slot is not assigned to ring #2, decision step94jumps back to step92to send a TTI to the subscriber assigned next time slot in ring #1. If the current time slot is assigned to ring #2, step96rotates the time slot in ring #2assigned to the current time slot in ring #1.

Decision step98jumps back to step92, transmitting a TTI to the subscriber22assigned to the next time slot in ring #1when the previous time slot in ring #2is not assigned to ring #3. If the previous time slot in ring #2is assigned to ring #3in decision step98, step100rotates the time slot in ring #3assigned to the previous time slot in ring #2. If decision step102determines the time slot for ring #4is assigned to ring #5, step104rotates the time slot in ring #5assigned to the previous time slot in ring #4. The number of logical rings is increased or decreased by reconfiguring the head end18.

Referring toFIG. 5, the TSLR protocol is configured for 5 ring levels in block70. Ring levels are dynamically assigned to subscribers22(FIG. 1) according to the frames received by the head end18in step72. Any number of ring levels can be configured in the TSLR. Alternative systems of schemes can be used for promoting and demoting the subscribers to different ring levels as described in further detail below.

Level1is used for burst transfers, such as file transfers. Level1is assigned to the current active subscribers in step76. The aging time on ring level1is less than a first time period, for example, some time period between 50 ms to 1 second, as determined in decision step74. This keeps the top ring level small, so that the current subscribers are assured the maximum access to the upstream bandwidth when initiating file transfers. Level2is assigned to subscribers in step80who aren't currently sending data, but might at any moment. The aging time interval is somewhere between 5 minutes to 30 minutes as determined in decision step78. The second aging time relates to subscribers who are currently inter-facing with a screen. The bulk of the active subscribers22would be in level2.

Subscribers22who are less active, are assigned to ring level3in step84. These subscribers have initiated a session with some far end host over the cable modem network12, but get data infrequently, as they are working locally on their PC52. (FIG. 2) An example application is a local PC52connected to the internet for mail access only. The aging time on level3is between 2 to 6 hours as determined in decision step82which represents an average session time.

Ring level4is assigned all other subscribers22in step88that are currently powered up but are inactive. Any subscriber22that is not on level1,2, or3, but is issuing heart beat frames as detected in decision step86exist at level4. Heart beat frames are described in further detail below. Ring level5represents the remaining subscribers that are powered down. Any subscriber22not transmitting a heart beat frame but is known to exist as assigned to level5in step90.

The multi-level scheduling in TSLR achieves a balance between quick access time, and the bandwidth available to the subscriber22once he becomes an active user. The TSLR protocol achieves this objective by classifying the subscribers22. Level 1 TSLR subscribers have the quickest access time and the largest percentage of network bandwidth available to them. Level 5 TSLR subscribers have the longest access time and the lowest percentage of the network bandwidth.

Different rules are used for promotion between rings. The simplest rule is that any subscriber22at any level that sends a frame gets immediate promotion to level1. A more advanced rule set promotes a subscriber22up through the levels based upon his level of activity. For example, for each frame transmitted, a subscriber is promoted up one ring. Therefore, a new subscriber has to transmit four frames within a short time interval to be promoted all the way from level5to level1.

Aging rules then demote the subscriber down to the appropriate level. In addition, subscribers which are limited in their interface rate may also be limited on how high up the level hierarchy they can go. For example, a 10 Mbps ethernet subscriber can be promoted all the way up to level1so that the total ethernet bandwidth can be used effectively. However, a 28.8 kbps subscriber is only allowed to be promoted as high as level3since level3meets the subscribers bandwidth requirements, and keeps the low bandwidth subscriber out of the way of high bandwidth subscribers.

TTI Metering

The amount of bandwidth a subscriber receives relates to how much the subscriber is willing to pay. A cable company can limit the bandwidth for particular subscribers so that “classes of service” may be established against a particular rate schedule. The TSLR protocol inherently control subscriber's bandwidth through the TTI issuing protocol. The bandwidth to any subscriber is limited by the number of TTI's issued within a given time frame. Essentially, TTI's are “metered” out to the subscriber.

The multi-level scheduling lowers access latency by increasing the user's priority based upon his network usage. The TTI metering protocol limits the total number of TTI's sent to the subscriber within a given time frame. In one implementation, a subscriber gets promoted up the logical ring structure as before, but once one of the TTI's is sent out, the subscriber remains at the current level and is passed over for another TTI until a fixed time between his TTI's is met. In a more complex implementation, a leaky bucket protocol is employed where the user is given a certain amount of time-bandwidth credits. As TTI's are issued, the credit count is decreased; as a configured time interval passes, the credit counter is increased. The credit count has a fixed maximum value. When the credit count hit zero, no more TTI's are issued until the particular time interval chosen had passed, and a credit was issued. The TSLR can also monitor the returned TTI's, and assign different weighting factors to used TTI's versus unused TTI's.

The leaky bucket protocol acts as a low pass filter. Short traffic bursts are allowed through at peak network bandwidth rates, but the overall average traffic is limited to a particular rate. The fixed TTI time interval limits both peak and average bandwidth, while the leaky bucket protocol limits more the average bandwidth and lets the peak bandwidth through. Since data tends to be very bursty, the leaky bucket protocol gives better performance to the subscriber at a lower class of service, while the fixed TTI time interval makes a subscriber more interested in increasing his class of service. Depending upon the class of service definition, either protocol may be employed.

TTI metering works in parallel with the hierarchy of logical rings. For example, if there is only one subscriber at level1who has an interface bandwidth of 100 kbps (either because of interface type or because of the class of service assigned), it would not make sense to give the level1subscriber every other TTI. Instead, other subscribers from level2and level3are allowed to use the idle time. This is done by assigning lower ring level subscriber more time slots on the level1ring.

Scheduling

Referring toFIG. 6, the downstream path14has one media with one transmitter at head end18and many receivers in subscribers22. Since there is only one transmitter, the head end18always has access to the media24and26(FIG. 1). The head end18broadcasts data to cable modem receivers in all subscribers22. Appended to the beginning of each frame92sent by the head end18is a subscriber identifier100. When a subscriber22matches the subscriber identifier100in frame92, the subscriber22receives the frame92. Otherwise, the subscriber22discards the frame92. All regular data traffic is directed in this manner towards individual subscribers22. A series of subscriber identifiers100are reserved for broadcast/multicast use.

However, the downstream media must support the TSLR TTI's92for the upstream protocol. Since the downstream is a broadcast media with only one transmitter, there is no need to utilize the logical ring portion of TSLR on the downstream path14. As frames are injected into the head end18by an external router or host38(FIG. 2), the frames92are set on a first come, first serve basis towards the subscribers22. TTI metering is run in the downstream direction14at the head end18to prevent putting frames92onto the network that cannot be used, or to enforce a class of service. Since frames92are sent down back to back, packet aggregation is not required in the downstream direction. Early TTI release is also not applicable in the downstream since the frames are being sourced from the controlling end.

Early TTI Release

If the TSLR network is configured for large frames, and a subscriber22returns a small frame with a returned TTI, that returned TTI arrives at the head end18long before the next downstream TTI is scheduled to be sent out. The early TTI release option recognizes the returned TTI, and then issues a new time tick identifier frame in a queue.

This allows 1500 byte frames and 64 byte frames to be intermixed without a significant loss of bandwidth. The amount of time not recoverable is equal to the head end18to subscriber22round trip propagation delay plus the TTI turn-around time at the head end18and at the subscriber station22minus the packet transition time. A numerical example is provided below.

Early TTI release loses its effectiveness if a subscriber22does not return any frame and the head end18is forced to wait the full time tick period. The solution to this problem is to have subscribers22return heart beat frames118when they do not wish to send data. The heart beat frame118is a short frame that confirms the existence of the subscriber, and allows the TSLR early TTI release to move on to the next station. As a result, time ticks sent by the head end18are not evenly spaced in time, and subscriber modems do not make assumptions on the time tick arrival time.

Frame Aggregation

Smaller frames will lower the bandwidth efficiency considerably, unless several smaller frames are transmitted as a group within the time tick window. This is referred to as frame aggregation. The subscriber station22has knowledge of the maximum transmission window (time slot), and packs as many small frames into it as possible, followed by the returned data frame, such as data frame95. This works well when there is a local queue of packets at a subscriber interface. This is not always the case for a casual subscriber who may be sending upstream keystrokes from his keyboard. However, in performance benchmark cases where large numbers of small packets are sent, frame aggregation significantly improves network performance. By performing the early TTI release and frame aggregation, network bandwidth efficiency is improved.

An “early TTI release” is a frame118that is returned by a subscriber22when it receives a TTI frame92, but has no data to send upstream. This heart beat frame118allows the early TTI release protocol to issue the next TTI93, rather than waiting for a maximum time-out interval. Instead of just being a null frame, the heart beat frame118contains basic information about the cable modem, such as the cable modem's subscriber identifier100(its serial number), its interface type (e.g., ethernet, Serial, Ti), and its configured speed (e.g., 28.8 kbps, 10 Mbps). The subscriber identifier100in each TTI frame is used by the subscriber's cable modem to identify the TTI. The head end18is configured with an access table99of the permitted identification numbers allowed per network. The access table99gives the network some level of security because unauthorized cable modems would not be given permission to transmit, and would not be sent any directed downstream traffic.

When a cable modem for a new subscriber22is configured into the network, the head end18assigns the modem to a lowest TSLR ring (ring #5in the example given inFIG. 5). When the subscriber22powers up the cable modem and begins transmitting heart beat frames118, the head end18moves the subscriber to TSLR ring4. If the heart beat frame100ever disappeared, the head end18times out while waiting for the returned heartbeat frame118. The head end18then moves the subscriber22in question back to ring5.

Heart beat frames118only consume a fraction of the network bandwidth under busy network conditions because subscribers sending heart beat frames118are not sending data and therefore are lower on the ring structure and have a long time between their TTI's. When a data frame is sent for example, data frame95in response to the TTI frame93from subscriber #4, the head end18waits a necessary amount of time before sending the next TTI frame97to the subscriber22assigned to the next time slot in the TLSR ring.

When none of the subscribers22have any data to transmit, the network is full of heart beat frames118, allowing for quick diagnosis of any new network problems. The heart beat frames118can have an extended format which could contain an entire Management Information DataBase (MIB) for a simple network management protocol (SNMP) and network management use. For cable plant diagnostics, the head end18commands all cable modems in all subscribers22to begin transmitting heart beat frames118at the subscriber's configured maximum transfer unit (MTU). With all modems transmitting maximum size frames on upstream path16, the head end18checks the guard band between all frames as they arrive at the head end18to make sure there is no overlap between subscriber modems that might be contributing to network data corruption.

Even for normal traffic, the head end18keeps statistics on the dead time between frames to make sure it is sufficient to prevent frame overlap, but not excessive to cause loss of service bandwidth. The minimum inter-frame gap will be a configuration parameter of the head end18and is related to the geographical size of the local node20. By using the heart beat frames118set to their maximum MTU size, this parameter is measured and auto-configured by the head end18.

TSLR MAC Layer Framing

Referring toFIGS. 7-9, one embodiment of the invention includes the TSLR MAC framing mechanism located in MAC's34and45and are independent of the TSLR MAC link management entity. Other framing methods can also be implemented. The TSLR framing layer provides the following services:1. Frame demarcation downstream and upstream.Method of inserting unique time tick identifiers and tags in the downstream path at arbitrary intervals for use with upstream traffic control.An error checking code.The ability to have frames back-to-back in the downstream direction with minimum overhead.Reduction of overhead on upstream frames.The ability to identify individual nodes.

In one embodiment, TSLR uses a variant of high level data link control (HDLC) for MAC layer framing. However, any interface can be used in combination with the invention. HDLC framing is an international specification that has been in use for years as an IOS Layer2framing protocol on wide area network connections such as X.25, frame relay and PPP. HDLC provides the basic functions of frame demarcation and error detection, while maintaining low overhead and back-to-back frame performance. In the downstream direction, TSLR uses a variant of HDLC called pre-emptive HDLC to allow TTI's to be arbitrarily embedded in the data stream. Pre-emptive HDLC allows a TTI frame to be inserted at any bit boundary between or within a data frame. In the upstream direction, standard HDLC is used with provisions for idle mark, flag preamble if needed, and packet aggregation. The payload of the TSLR MAC layer is independent of the MAC layer and could be PPP, encapsulated ethernet frames, ATM or voice.

Downstream Framing

FIG. 7shows the HDLC format used to frame the data frames in the downstream direction. TTI's, which are also in the downstream, are HDLC frames with a different tag. The structure of a data frame98for downstream TSLR HDLC framing begins with an opening flag94or 01111110. The uniqueness of this 8 bit pattern is guaranteed by adding (stuffing) and subsequently removing (stripping) a zero after any sequence of five ones. The first byte after the flag is a tag byte96. A tag96identifies the packet as a data frame98or as a TTI frame92. Additional functions of the tag96are discussed in further detail below. The tag96is the first byte after the flag94to allow immediate frame filtering and classification by hardware steering logic.

A subscriber identifier100is usually the manufacturer's serial number of the cable modem. The subscriber identifier100identifies which cable modem should receive the frame98. A traditional address and control field of HDLC is replaced by the tag96and the subscriber identifier100. A payload102of the frame98is the data packet (such as a PPP packet) being moved across the network. It is followed by a cyclic redundancy code (CRC)104to guarantee maximum data integrity and a closing flag106. The downstream idle character is a repeating flag sequence. The edges in the idle flags allow downstream phase locked loops (PLLs) to remain locked. Frames92and98may be aborted by the transmitter by inserting six or more ones within a data frame. Opening and closing flags may be shared.

The TTI frame92begins with an opening flag94. The tag96identifies the frame as a TTI frame. The subscriber identifier100contains the ID of the subscriber22who is next allowed to transmit upstream. There is no payload. The TTI frame92ends with a CRC104and a closing flag106.

Referring toFIG. 8, the TTI frame92is inserted beginning at any bit position in the downstream data path (pre-emptive HDLC). If a data frame98is being received and a single flag94occurs, the receiver checks the tag96to determine whether the flag94is a closing flag for the current frame98, or is an opening flag for the TTI frame92. If two flags occur in sequence, it is assumed that the first flag was a closing flag for the previous frame. The bit stuffing and stripping calculations for two interlaced packets are kept separate. In this manner, steering logic can intercept the TTI frames92and route them away from a data HDLC controller and into a second HDLC controller.

Upstream Framing

Referring toFIG. 9, the upstream data path16(FIG. 1) represents a many to one mapping, and therefore, naturally tends to have contentions. The downstream TTI frames92, however, institute an orderly environment where only one subscriber will transmit at a time, thus eliminating contention. Initial response times and latencies are dealt with in the TSLR MAC layer link management entity running at the head end18.

The upstream TSLR framing uses a standard, non pre-emptive, HDLC format. An idle mark116is used between frames118. Idle mark116refers to an idle pattern of all ones. This means the media can default to a logic high when there are no subscriber nodes transmitting, and all receivers will perceive this as idle. When the particular subscriber22receives a TTI frame92, the frame118is launched. The frame118could be data frame, a heart beat Frame, or a frame aggregation frame. The differentiation is made by the tag96. The subscriber identifier100is the source id of the frame116, and is therefore, the same id sent in the TTI frame92. The payload102is null if the packet is a heart beat frame without any extended information or a data packet from the attached network. The payload102is followed by a CRC104. The tag96is different between a TTI frame and a heart beat frame, so the CRC104will have to be recalculated. The frame118ends with a closing flag106.

If frame aggregation was indicated in the tag96, another frame immediately follows. Idle marks116are not allowed between frame aggregation frames, but multiple flags are permitted so long as the total number of bytes in the entire multi-frame sequence does not exceed the frame aggregation maximum transfer unit (FA-MTU) allowed by the head end TSLR. Once the data transmission is finished, the subscriber transmitter releases the media, and the media defaults to all ones. The length of idle depends upon the TSLR protocol configuration values being used at the head end18.

Tag Byte

The tag byte96includes bit definitions listed below and further described inFIG. 11. Direction Bit: This bit identifies the packet as an upstream or downstream packet. This bit is used with the ID bit, and is also useful for network diagnostics. Identification Bit: This bit identifies a data packet, a downstream packet as a TTI, and an upstream packet an a heart beat packet. Frame Aggregation Bit: Used in the upstream direction to identify a single frame is being sent, whether another frame will be sent immediately following the current frame. Expansion Bit: This bit identifies a simple TTI or a simple heart beat and whether there is a payload.

TSLR Physical Layer Requirements

The physical layer of the cable media provides the following services: downstream data link, upstream data link, and a synchronized clock and data interface at both ends of the link. As the data passes through the interface at either end of the TSLR network12shown inFIG. 1, there must be a separate clock signal and a separate data signal. On the TSLR internal media24and26, clock and data are typically combined together. This leads to the requirement of a clock recovery circuit at each end of the TSLR media.

In the downstream direction14, all bits are generated off of one master clock at the head end18, so each subscriber node20can synchronize with a PLL to the master clock. The downstream idle character contains edge information, so a lock will always be maintained. This is true even though each subscriber22is located at a different distance from the head end18. In the upstream direction16, clocking is more difficult. Since each subscriber22is a different distance from the head end18, frames arriving at the head end18will all be at the same frequency, but at different clock phases. This is assuming that the subscribers22are using the downstream clock to generate the upstream clock. If the upstream clock is free-running, then the problem is even more difficult.

TSLR provides two solutions for upstream clock recovery. The first solution attaches a preamble of bits to the beginning of the frame to provide time for a phase locked loop to lock on. This preamble is in the upstream direction only and is a sequence of HDLC flags. Most HDLC controllers have the ability to send a minimum number of frames between flags. External gating of the HDLC controller provides the all ones idle. The second solution uses the head end master clock as a frequency reference, (assuming accurate PPL in the network), digitally over samples the incoming signal, mathematically determines its phase, and then extract the data. Phase and frequency shifts during a maximum length packet are limited to a fraction of the clock cycle, depending upon the oversampling ability.

TSLR Cable Modem Hardware Block Diagram

A high level block diagram of a TSLR cable modem is given inFIG. 10. The RF demodulator122extracts from the CATV coax26raw data from the RF spectrum and physically formats it into a clock stream and a data stream with a PLL124. The RF modulator122does the opposite function of taking base band clock and data streams and up converting them into a RF spectrum transmitted on the coax26. On receive, steering logic120checks the tag byte96and separates out TTI frames92from data frames98(FIG. 7). On transmit, the steering logic120enables one of the HDLC controllers HDLC0or HDLC1to send data, if there is data queued up, or a heart beat frame118if no data is queued up. After the packet transmission, the steering logic120disconnects the HDLC0or HDLC1and returns the line to mark idle.

All the data traffic goes through HDLC0. HDLC0direct memory accesses (DMA's) data frames from the line into RAM126, and from RAM126back to the line. All TTI's and heart beat frames go through HDLC1. Since non-extended TTI's and heart beats (refer to tag byte values) do not need intervention from CPU128, HDLC1can be simpler in design than HDLC0. The CPU128provides the local switching function that prevents local frames between local computers52(FIG. 2) from getting into the cable modem network12. CPU128also manages a local queue of packets that are waiting for TTI's, frame aggregation, and local diagnostics.

For a network bandwidth of 30 Mbps downstream and 10 Mbps upstream. The minimum length between TTI's is:

1ushead end response time3.2usTTI downstream transition time14usdelay in local node network1ussubscriber turnaround time11.2heart beat upstream transition time5usguard band35.4usTotal
The maximum time between TTI's with a 1,500 byte frame instead of a heart beat frame: 35.4 us−11.2 us+1,200 us=1,224 us. The minimum length of time between time tick frames in this example is affected only by the first three items, and is about 25 microseconds plus the frame transition time. Without the TSLR “pipe-lining” effect of having multiple TTI's issued, the minimum length of time between time ticks is 145 microseconds plus the frame transition time. The frame transmission time for a long frame is many times greater than the local propagation delay. That means that almost all the upstream bandwidth can be used for data transmission, and that the maximum data transmission rate will approach 100% efficiency.

The Time Slotted Logical Ring protocol manages the flow of traffic in a duplex media. This duplex media has a local area to it which is tree structured, and a remote controlling processor which is connected with a long haul link. The specific implementation is a cable distribution network with a head end, a local node, and a group of subscribers.

The subscriber node includes a cable modem which produces an HDLC serial interface which then goes to the subscriber or gets converted to ethernet by a router and then to the subscriber. Conversions to ISDN, ATM, or other interfaces can also be done, depending upon the payload data type. The Time Slot portion of TSLR protocol manages upstream and downstream access and uses time ticks, tags, and TTI's in the downstream direction to control upstream traffic. The frame aggregation and early TTI release algorithms improve bandwidth performance for short frames.

The logical ring portion of TSLR manages upstream bandwidth and access time by classifying subscribers into hierarchical levels based upon their network usage. Subscribers who are actively using the network are given shorter access times and high bandwidths by a system of ring promotion and demotion. The Lower Ring Access Interval controls how much of the active bandwidth is used to survey non-active users. Downstream bandwidth management does not use the ring hierarchy. Instead, frames are sent on a first come, first serve basis from the head end. TTI metering is used to make sure that excessive TTI's are not wasted on a lower bandwidth subscriber, and also to provide a means for defining classes of service.

Because TSLR minimizes interframe gaps for any size frame and dynamically allocates more bandwidth to busier users, TSLR could support wire speed ethernet rates simultaneously from different subscriber nodes up to the physical bandwidth of the network media. The TSLR protocol is highly efficient over a large geographically distributed media, and is extendable to data, voice, ATM, or any mixture, and is usable to back end a variety of physical layer interfaces such as ethernet, ISDN, ATM, or serial.

Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention can be modified in arrangement and detail without departing from such principles. I claim all modifications and variation coming within the spirit and scope of the following claims.