HK1178343B - Scheduling in a two-tier network - Google Patents

Abstract

The invention provides a method, system and computer program product to schedule transmissions in a two-tier network. In an example, the system includes a Data over Cable Service Interface Specification (DOCSIS) scheduler configured to generate a MAP message to allocate bandwidth and a first instance in time to a cable modem to transmit data to a branch node. The system further includes a MAP message translator coupled to the DOCSIS scheduler and configured to determine a second instance in time at which data from the cable modem arrives at the branch node and generate a GATE message that grants the branch node bandwidth to transmit the data received from the cable modem at the second instance in time to a headend node.

Description

Scheduling in a two-tier network

Cross Reference to Related Applications

This application claims benefit from U.S. provisional application No. 61/525,485 filed on 8/19/2011 and U.S. utility application No. 13/538,079 filed on 6/29/2012, the entire contents of which are incorporated herein by reference.

Technical Field

The present invention relates generally to scheduling in point-to-multipoint networks.

Background

A two-layer network comprising different media (e.g., optical media and coaxial media) presents difficulties in scheduling transmissions to and from end stations due to differences between protocols used via the different media. Methods and systems are needed to overcome these deficiencies.

Disclosure of Invention

One aspect of the present invention provides a head-end node for scheduling uplink transmission time in a dual-layer network, including: a scheduler configured to generate a first message to allocate bandwidth and a first time instance for an end station to transmit data to a branch node via a branch medium of the two-tier network; a message converter coupled to the scheduler and configured to determine a second time instance of arrival of data from the end station at the branch node and generate a second message granting the branch node bandwidth to transmit data received from the end station at the second time instance to a head-end node over a backbone medium of the dual-tier network.

Wherein the scheduler is a Data Over Cable Service Interface Specification (DOCSIS) scheduler, the end station is a cable modem, the first message is a MAP message, the second message is a GATE message, the backbone medium of the dual layer network is an optical medium, and the branch medium of the dual layer network is a coaxial cable medium.

Wherein the scheduler is configured to receive bandwidth requests from the branch nodes, wherein the requests originate from the end stations coupled to the branch nodes over the branch medium.

Wherein the scheduler determines the first time instance (the first time in time) and an amount of bandwidth to allocate to the end station based on a quality of service (QoS) and a service level agreement associated with the end station.

Wherein the node further comprises a time base coupled to the scheduler, the scheduler configured to determine the first time instance based on data received from the time base.

Wherein the node further comprises a time base coupled to the MAP converter, the MAP converter configured to determine the second time instance based on data from the time base.

Wherein the node further comprises a Passive Optical Network (PON) Physical (PHY) layer for transmitting the MAP message and the GATE message, wherein the branch node stores and processes the GATE message and forwards the MAP message to the cable modem.

Another aspect of the present invention provides a branch node, including: a first downstream physical layer (PHY) configured to receive a first message and a second message from a head-end node; and a second downstream physical layer coupled to the first downstream physical layer and configured to transmit the first message to a terminal station; wherein the second message specifies a second instance in time at which the branch node transmits data received from the end station to the head-end node, wherein the second instance in time is approximately equal to the time at which the branch node receives the data from the end station.

Wherein the first downstream physical layer is a passive optical network downstream physical layer, the second downstream physical layer is a Data Over Cable Service Interface Specification (DOCSIS) physical layer, the first message is a MAP message, the second message is a GATE message, the end stations are cable modems, and the head-end node comprises a Cable Modem Termination System (CMTS).

Wherein the branch node is coupled to the head-end node through a Passive Optical Network (PON) and to the cable modem through a coaxial network.

Wherein a node further comprises a buffer configured to store data received from the end station prior to transmission of the data to the head-end node.

Yet another aspect of the present invention provides a method for scheduling uplink transmission time in a dual-layer network, including: generating a first message to allocate bandwidth and a first time instance to a first device for transmitting data to a branch node; and generating a second message granting the branch node bandwidth to transmit the data received by the first device at the second time instance to a head-end node.

The method further includes receiving a bandwidth request from the branch node, wherein the request originates from the first device.

The method further includes determining a first time instance and an amount of bandwidth to allocate to the first device based on a quality of service (QoS) and a service level agreement associated with the first device.

Wherein the first device is a cable modem and the head-end node is a Cable Modem Termination System (CMTS).

The method further includes determining the first time instance based on data received from a DOCSIS time base.

The method further includes determining the second time instance based on data from a Passive Optical Network (PON) time base.

Wherein the first message is a MAP message and the second message is a GATE message.

The method further includes transmitting the MAP message and the GATE message, wherein the breakout node stores and processes the GATE message to determine the second time instance and forwards the MAP message to the cable modem that stores and processes the MAP message to determine the first time instance.

Drawings

The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the principles of the invention. In the drawings:

fig. 1 shows the topology of a two-layer network.

Fig. 2 shows an example two-tier network where the main medium is a Passive Optical Network (PON) and the branch medium is a coaxial cable.

Fig. 3 shows decentralized scheduling in a two-layer network.

Fig. 4 illustrates centralized scheduling in a two-layer network.

Fig. 5 illustrates an example two-tier network with minimal buffering and scheduling delay.

Fig. 6 illustrates an example flow chart showing steps performed by a head-end node for scheduling in a two-tier network.

Fig. 7 illustrates an example flow diagram showing steps performed by a branch node in a two-tier network.

FIG. 8 illustrates a block diagram of an exemplary computer system, in which embodiments can be implemented.

The present invention will now be described with reference to the accompanying drawings. In the drawings, like reference numbers may indicate identical or functionally similar elements.

Detailed Description

Although the examples are described herein with reference to illustrative embodiments for particular applications, it should be understood that the examples are not limited thereto. Those skilled in the art with access to the teachings provided herein will recognize additional modifications, applications, and embodiments within the scope thereof and additional fields in which the embodiments would be of significant utility.

A common architecture of a two-way communication system is a point-to-multipoint network via a shared medium. One example is a data-over-cable communication system, such as a Data Over Cable Service Interface Specification (DOCSIS) compliant communication system. In the system, a single head-end node, which may include a Cable Modem Termination System (CMTS), communicates with multiple end user nodes (e.g., Cable Modems (CMs)) over a shared coaxial cable or Hybrid Fiber Coaxial (HFC) medium. The "coaxial cable" may be referred to herein as the "coaxial medium" or "coax". Another example is a wireless Wi-Fi system in a typical home network where a single wireless base station may communicate with multiple user devices over a shared frequency band in the wireless spectrum. Another example is a cellular system in which a single cellular base station may communicate with multiple handheld terminals in the same frequency band. Yet another example is a Passive Optical Network (PON) in which a single Optical Line Terminal (OLT) communicates with multiple Optical Network Units (ONUs) over a shared optical medium.

In these types of two-way communication systems, only a single device may communicate via a designated channel or portion of a channel at any given time. The protocol used on the network determines which device uses the channel or a designated portion of the channel at any given time. In the Open Systems Interconnection (OSI) model, the Medium Access Control (MAC) layer typically determines the transmission order of end user devices. In DOCSIS, PON, and other systems, a scheduler located in the head-end node (e.g., the CMTS in a DOCSIS network or the OLT in a PON network) determines when and how long each end station (e.g., the CM in a DOCSIS system or the ONU in a PON system) uses the communication medium. In the downstream direction (i.e., from head-end node to end station), the head-end node is merely a transmitter, and thus can autonomously decide when to store data in which end station and then transmit the data. In the upstream direction (from the end stations to the head-end node), the scheduler at the head-end transmits messages to each end station so that it knows when it is allowed to transmit data to the head-end node and the length of time it can transmit data.

There are a number of possible algorithms that the scheduler can use to determine when and how much traffic to allow to each end station. For example, the scheduler may use a round-robin or weighted round-robin approach to provide a substantially constant bandwidth to each end station. In a packet-based communication system, a scheduler may incorporate a request-grant mechanism. In the request-grant mechanism, the scheduler specifies the time slots that the end stations can use to report information about the amount of data they must or desire to use for transmission. The scheduler transmits messages to the terminal stations to inform them of the time slots. After the terminal stations respond, the scheduler uses the information received about the amount of data on each terminal station, as well as other information (e.g., the type of traffic and the quality of service (QoS) processing required for each request) to allocate time slots to the terminal stations transmitting the data; a message containing information about these data transmission slots is transmitted to the terminal station. Finally, the terminal station responds by transmitting data during the allocated time slot.

For non-constant traffic, the request-grant mechanism is preferably used (e.g. for best effort traffic for Web browsing, which exhibits a short activity mixed with a long idle period) because it only allocates bandwidth to the end stations when this station has traffic to send. This allows for statistical multiplexing of media (e.g., coax media), with higher utilization and better performance. A disadvantage of using the request-grant mechanism is that an additional source of delay is introduced into the upstream path. A terminal station having data to be transmitted must wait for the scheduler to provide an opportunity to request bandwidth for data transmission and then wait for the scheduler to provide a time slot for data transmission.

For constant bandwidth traffic (e.g., voice traffic), it is generally desirable to avoid the use of the request-grant mechanism. In contrast, the scheduler uses priority information about the traffic to schedule data transmission opportunities available to the terminal stations without requiring the terminal stations to first report data availability. For example, if an end station is engaged in an ITU-T standard g.711 voice over IP (VoIP) telephone call at 20ms packet intervals, the scheduler provides a transmission opportunity of approximately one g.711 data packet per 20 ms.

The scheduler may employ a combination of various approaches. For example, the request-grant mechanism may be used for some types of traffic from end stations, while it is not used for other types of traffic. Taking this as an example, in DOCSIS, a traffic flow of constant bandwidth Unsolicited Grant Service (UGS) may be used for real-time voice calls from a device, while a request-grant mechanism may be used for best-effort data traffic from the same cable modem.

UGS traffic flow minimizes latency with respect to VoIP packets while the request-grant mechanism maximizes network efficiency for best-effort traffic data at the expense of increased latency. In theory, best effort traffic flows are delay tolerant. In practice, however, the performance of UGS traffic flows may be negatively impacted by the increased delay. For example, if the delay of a TCP Acknowledgement (ACK) message returned in the upstream is low, a downstream Transmission Control Protocol (TCP) flow using a slow start algorithm may increase to maximum speed in a short period of time. Excessive delay of the upstream TCP ACK may prevent the downstream from permanently reaching the maximum rate. Also, request-grant mechanisms may be used for traffic that exhibits bursty data patterns and/or traffic with variable bandwidth requirements, but is still sensitive to latency, such as two-way video conferencing using variable bit rate compression, or real-time gaming or cloud computing traffic that requires user keystrokes to be transmitted to a remote server as quickly as possible. It is therefore desirable to minimize the delay added by the request-grant mechanism in a point-to-multipoint system.

It is also possible to have a dual layer point-to-multipoint network. Fig. 1 shows an example of a two-layer point-to-multipoint network 100 according to an embodiment. The network 100 includes a head-end node 102 coupled to branch nodes 104a-n by a backbone medium 103. The backbone medium 103 forms the first layer of the two-layer network. Branch nodes 104a-n are coupled to end stations 108a-n through branch mediums 106 a-n. The branch mediums 106a-n form the second layer of the two-layer network.

In network 100, head-end node 102 communicates with a plurality of end stations 108 over a shared medium (e.g., backbone medium 103). Branch node 104 may replicate and provide some or all of the traffic of head-end node 102 to end station 108 via branch medium 106. The topology can be extended to systems comprising more than two layers. For example, one or more of the second tier of end stations 108 in turn provides functionality as a branch node to additional end stations through other media. It should be appreciated that while the examples presented herein are described with reference to a two-tier system, the examples are applicable to networks of more than two tiers.

Fig. 2 shows another example of a two-tier network 200. In network 200, trunk medium 103 is an optical medium, such as a PON, and branch medium 106 is a coaxial cable. An Ethernet Passive Optical Network (EPON) protocol may be used to schedule transmissions over the backbone medium 103 and a DOCSIS protocol may be used to schedule transmissions over the branch medium 106. Due to differences between protocols in the network 200, the backbone medium 103 and the branch medium 106 must be scheduled separately. Therefore, a two-tier scheduling must be performed for the two-tier network. In addition to scheduling delays, double-tier scheduling causes buffering.

Another example of a two-tier network is a Wi-Fi home network that includes one or more repeaters or "range extenders". Wi-Fi repeaters, typically sold for homes, create independent wireless networks from a primary Access Point (AP) or base station. Thus, each repeater may serve as a branch node 104 that may reach multiple end stations. In this example, the trunk medium may be a PON, coaxial cable, or Wi-Fi from the primary AP, and the branch medium is an additional Wi-Fi channel. The media of the various branch nodes may partially or completely overlap each other or the backbone media, and therefore the transmission timing of the entire branch must be coordinated.

It should be understood that each of the branch mediums 106 may be a different medium. For example, branch medium 106a may be a wireless medium and branch medium 106n may be an optical medium, each having independent scheduling requirements. In the example presented herein, the trunk medium uses the DOCSIS standard, while the branch medium uses the EPON standard. However, in alternative embodiments, the backbone media may use the EPON standard and the branch media may use the DOCSIS standard. It should also be understood that although the embodiments presented herein are described with reference to the DOCSIS standard and the EPON standard, the embodiments are not limited to any particular type of standard, protocol, or network configuration, i.e., any type of standard, protocol, or network configuration may be used for both the backbone medium and the branch medium.

In any point-to-multipoint network with multiple layers, it must be decided where in the system the scheduling function should be located. The scheduling may be distributed among multiple nodes, centralized at a single node, or some combination of the two. Fig. 3 illustrates an example network 300 that uses decentralized scheduling in a two-layer network. In the example of FIG. 3, the head-end node 102 schedules each of the branch nodes 104 a-n. Each branch node 104 in turn schedules its associated end station 108. For example, the head-end node 102 includes a scheduler 306 that schedules each of the branch nodes 104a-n by communicating with the backbone medium (MM) terminals 307 a-n. Similarly, each scheduler 308a-n schedules a respective end station 108 that is part of the network in which the respective scheduler 308 is used. Scheduler 306 may include, for example, some or all of the functionality of an EPON scheduler. The scheduler 308 may include, for example, some or all of the functionality of a DOCSIS scheduler.

In an example, end stations 108 request bandwidth from respective branch nodes 104 to transmit data. Branch node 104 schedules the request and issues a bandwidth grant to end station 108 using scheduler 308. End station 108 grants transmission of data packets to branch node 104 based on the received bandwidth. Upon receiving a data packet from an end station 108, the branch node 104 sends an "EPON REPORT" to the head-end node 102 to request bandwidth for the received data packet. The scheduler 306 schedules and issues bandwidth grants to the branch nodes 104. In response to receiving authorization from scheduler 306, branch node 104 transmits data packets received from end station 108 to head-end node 102. The head-end node 102 then forwards the data packets over a wide area network, such as the internet (not shown).

The decentralized scheduling described above with respect to fig. 3 appears straightforward but may have drawbacks. For example, the complexity of the cost of each branch node 104 may be costly because each branch node 104 includes logic circuitry and processing power to support the scheduling functions performed by the scheduler 308. In addition, in the upstream direction, bandwidth requests received by head-end node 102 from branch nodes 104 may contain information only about the traffic aggregated at that node, i.e., information about the traffic of each individual end station 108 may not be provided by branch nodes 104 due to the limitations of the protocols used. The lack of information about end stations 108 may cause head-end node 102 to make less optimal scheduling decisions than decisions made with information about available traffic from each end station 108. For example, an end station 108 originating at a particular branch node 104 supporting multiple users may receive less traffic than end stations 108 on different branch nodes 104 supporting fewer users. The required corrective action may be used for the scheduler 306 in the head-end node 102 to increase the allocation of branch nodes 104 with more users. However, without information regarding the traffic requirements of individual end stations 108, scheduler 306 at head-end node 102 may be unable to perform the required allocation.

Furthermore, in the upstream direction, if the request-grant mechanism is used on both layers, traffic may experience two request-grant delays, since scheduling must occur once on the backbone medium 103 and then once again on the branch medium 106. This results in scheduling and buffering delays. For example, for upstream transmissions from a terminal station 108, the scheduler 308 must request the scheduler 306 for bandwidth for each transmission. Data received by branch node 104 from end station 108 must be buffered while scheduler 308 waits for a response from scheduler 306. This can lead to scheduling delays with accompanying buffering problems. For example, if the scheduling delay is excessive, the buffer in the branch node 104 may overflow. Additionally, scheduler 306 may not have the granularity to provide quality of service (QoS) for individual end stations 108 a-n. For example, scheduler 306 for backbone medium 103 can provide aggregate traffic to branch nodes 104, but cannot meet the individual QoS requirements of each end station 108.

Focusing the scheduling functionality in the head-end node 102 may solve some of the problems of decentralized scheduling. For example, the branch nodes 104 need not contain any scheduling functionality, so that they may be simpler and less costly. Additionally, for upstream traffic, the centralized scheduler in head-end node 102 will receive reports from all individual end stations 108, providing them with the information needed to make the best selection.

Fig. 4 illustrates an exemplary network 400 utilizing centralized scheduling. In the example of fig. 4, the head-end node 102 includes a DOCSIS CMTS 402 with a DOCSIS scheduler 403 and an EPON OLT404 with an EPON scheduler 405. The main medium 103 is a PON and the branch medium is a coaxial cable. In the example of FIG. 4, DOCSIS scheduler 402 schedules each end station 108 that may be a cable modem. Scheduler 402 transmits DOCSIS MAP messages that are used to allocate the requested bandwidth for end station 108. The EPON scheduler 404 grants bandwidth to the branch nodes 104 a-n. Each branch node 104 may include an EPON ONU 406 that forms a PON interface with the backbone medium 103. EPON ONU 406 is coupled to buffer 408, which buffers downstream and upstream communications to end station 108 or from end station 108. DOCSIS PHY 410 forms an interface with the coax cable of branch medium 106.

In an example, end stations 108 transmit DOCSIS requests for bandwidth to their respective branch nodes 104. In response to the DOCSIS request, branch node 104 sends an EPON REPORT to request bandwidth from EPON OLT404 to transmit the received DOCSIS request to EPON NOLT 404.

In response to the EPON REPORT, EPON OLT404 transmits an EPON GATE message using EPON scheduler 405 that allows branch nodes 104 to transmit DOCSIS requests received from end stations 108 to EPON OLT 404. EPON OLT404 grants bandwidth to transmit DOCSIS requests to branch nodes 104. Upon receiving the requested bandwidth, branch node 104 transmits a DOCSIS request to EPON OLT 404. EPON OLT404 transmits the received DOCSIS request to DOCSIS CMTS 402. DOCSIS scheduler 403 schedules and issues grants in a MAP message that is first sent to EPON OLT 404. EPON OLT404 transmits the MAP message to branch node 104, which then forwards the MPA message to end station 108.

Upon receiving the MAP message with the allocated bandwidth, end station 108 transmits data to branch node 104. The branch node 104, in turn, sends an EPON REPORT to the EPON OLT404 requesting bandwidth to transmit data received from the end station 108. An EPON scheduler 405 schedules EPON GATE messages to allow the branch nodes 104 to transmit received data to the head-end node 102. The branch node 104 transmits the data packets to the head-end node 102, which may forward the received data packets to the WAN.

As can be seen from the foregoing example, the centralized scheduling in fig. 4 presents problems when different MAC layer protocols are used by different layers of the network 400. As described above, in the system of fig. 4, the PON for the backbone medium 103 is controlled by the EPON protocol, and DOCSIS may be the preferred protocol for communicating with and managing end stations via the branch medium 106. Centralizing DOCSIS scheduler 402 forms the hierarchy of EPON system 414 surrounded by DOCSIS system 416 as shown in fig. 4. Because DOCSIS scheduler 403 cannot control traffic on the PON due to differences between protocols in network 400, the EPON request-grant mechanism operates within the DOCSIS request-grant mechanism. Centralized scheduling of network 400 may result in additional delays, as in the detailed example above, where DOCSIS requests to transmit available upstream traffic from end stations 108 are first received and buffered at branch node 104, followed by delays in the request-grant process completed over the PON, such that the original requests from end stations 108 may ultimately be sent to head-end node 102. When the head-end node 102 has allocated a time slot for data transmission, it passes this information to the EPON scheduler 405 for transmission to the branch node 104 and then to the end station 108. Finally, when end station 108 transmits its data, the data is received and buffered at branch node 104, which then needs to complete another request-grant cycle over the PON to transmit the data received from end station 108 to head-end node 102. It is clear that this centralized scheduling method results in more steps and thus increased delay when compared to the decentralized method.

Furthermore, the EPON scheduler 405 does not have knowledge of the quality of service (QoS) guaranteed for each end station 108. For example, end station 108a may have a first QoS associated therewith that is different than a QoS associated with end station 108 b. However, the EPON scheduler 405 allocates the total bandwidth to each branch node 104 and cannot support the QoS requirements of each end station 108 individually. Thus, the centralized scheduling shown in fig. 4 lacks granular QoS support.

One system that provides a possible solution to this problem extends EPON MAC layer protocols beyond branch node 104 and over the coax branch medium 106 to end station 108 utilizing PHY layer translation (translation) to accommodate the different characteristics of the PON and coax media. The single MAC protocol allows the head-end node 102 to control the scheduling of the PON layer and the coax layer of the network. However, in some cases, system providers prefer to retain DOCSIS protocols in end stations. For example, service providers may wish to take advantage of DOCSIS features to manage coax PHYs, or may wish to use existing DOCSIS cable modem and/or CMTS products that incorporate features such as routing or VoIP support.

Fig. 5 illustrates an example network 500 that minimizes buffering and scheduling delays. In network 500, main medium 103 is a PON, and branch medium 106 is a coaxial cable network. In this example, head-end node 102 includes a DOCSIS downstream media Access control (DS MAC) 502, a DOCSIS scheduler 504, a PON MAC 510, a DOCSIS timebase 506, a MAP converter (translator) 508, a PON timebase 512, a PON Transmission physical layer (PHY TX) 518, a PON reception physical layer (PHYRX) 514, and a DOCSIS upstream MAC (DOCSUS MAC) 516. Each branch node 104 includes an EPON ONU 520, a DOCSIS transmission phy (DOCSIS TX phy) 530, and a DOCSIS reception phy (DOCSIS RX phy) 532. EPON ONU 520 includes a PON receive PHY (PON rx) 522 coupled to a buffer 526 coupled to DOCSIS TX PHY 530. The DOCSIS RX PHY 532 is coupled to a buffer 528 that is coupled to a passive optical network transmission PHY (pon tx) 524. The PON TX 518 and the PON RX 514 form an interface between the head-end node 102 and the main medium 103, which in this example is a PON. PON TX 524 and PONRX 522 provide an interface between branch node 104 and backbone medium 103. DOCSIS TX PHY530 and DOCSIS RX PHY 532 provide an interface between branch node 104 and branch medium 106, in this example, branch medium 106 is a coaxial cable.

In network 500, for upstream communications, bandwidth requests transmitted by end station 108 are received by DOCSIS RX PHY 532, and end station 108 may be a cable modem. The request is buffered in buffer 528 and transmitted by PON TX 524 to head-end 102. The request is received by PONRX 514 and forwarded to DOCSIS upstream MAC 516, which in turn forwards the request to DOCSIS scheduler 504. In response to receipt of the request, DOCSIS scheduler 504 generates a MAP message that allocates bandwidth to the end station 108 requesting bandwidth based on QoS parameters associated with the flow corresponding to the request, service level agreements associated with the flow and/or the end station 108 generating the request, and possibly other considerations. The MAP message also specifies a first time instance for end station 108. The first instance in time is when end station 108 can begin transmitting data based on timing information from DOCSIS timebase 506. The MAP message generated by DOCSIS scheduler 504 is sent to MAN translator 508 and to DOCSIS DS MAC502 for transmission back to end station 108.

MAP translator 508 approximately determines a second time instance at which data from end station 108 arrives at branch node 104 based on the MAP message generated by DOCSIS scheduler 504, assuming end station 108 transmits data at the first time instance allocated in the MAP message. The MAP message must not contain any contention region because contention is not supported by EPONs. MAP translator 508 may store information such as the processing speed of branch node 104 and the transmission speed of branch medium 106 that allows it to approximately determine the second time instance at which data will arrive at branch node 104. MAP translator generates a GATE message based on PON timing information received from PON timebase 512, which allows branch node 104 to transmit data received from end station 108 beginning at approximately the second time instance to head-end node 102. The second time instance may accommodate timing and processing delays generated by end station 108 and branch node 104. Thus, the first instance in time is the time at which end station 108 may transmit data to branch node 104, and the second instance in time is a time substantially equal to or shortly after the time at which branch node 104 receives data from end station 108 and prepares to transmit the received data to headend node 102.

MAP translator 508 is aware of the PHY parameters used on the trunk medium 104 and branch medium 106 so that it can ensure that the size of the GATE allocation is sufficient to carry the amount of data transmitted by end station 108 during the MPA allocation process. MAP translator 508 must also be aware of the timing between DOCSIS and EPON systems, and the expected delay through branch node 104 from the time an end station 108 transmits a burst until the time it is processed by branch node 104 and ready for transmission to head-end node 102. It must be ensured that the GATE message contains the correct start-up time. To minimize the delay, GATE should start as soon as possible after the data is ready, but must not start before the data is ready or before a transmission opportunity is missed and another opportunity must be provided at a later time, resulting in an even further increase in delay.

The MAP message generated by the DOCSIS scheduler 504 is sent to the DOCSIS DS MAC502, which DOCSIS DS MAC502 transmits the MAP to the branch node 104 through the PON MAC 510 and PON TX 518. The MAP message is received by PON RX 522 in branch node 104a, buffered in buffer 526, and forwarded to destination end station 108 through DOCSIS TX PHY 530. The GATE message generated by MAP translator 508 is transmitted to branch node 104a through PON MAC 510 and PON PHY 518. Branch node 104a does not forward the GATE message to end station 108. The GATE message indicates a second time instance and a duration of time available for branch node 104a to transmit data received from end station 108 to head-end node 102.

Without the presence of MAP translator 508, upon receiving data from end station 108, branch node 104 must first buffer the data in buffer 528, and then request that head-end node 102 schedule a time at which branch node 104 may transmit the received data to head-end node 102. Branch node 104 must then wait until a GATE message is received from head-end node 102 that allocates bandwidth for transmitting the received data to head-end node 102. Thus, by scheduling the transmission times of end stations 108 and branch nodes 104 in the foregoing, MAP translator 508 substantially aligns the times at which branch nodes 104 receive data from end stations 108 with the times at which branch nodes 104 transmit data to headend node 102 to minimize scheduling and buffering delays. Buffering still occurs at the branch node 104, but for a minimum duration, because the upstream scheduling has been done "in advance" by the MAP translator 508. This example is characterized by the lack of a PON scheduler, which is why the DOCSIS scheduler in conjunction with the MAP switch schedules both layers in the network 500. This allows head-end node 102 to pre-allocate the requested bandwidth for transmission of data received from end stations 108 and also to time branch nodes 108 for transmission of data such that little buffering or scheduling delay is involved.

In an example, end stations 108 transmit DOCSIS requests for bandwidth to respective branch nodes 104. Branch node 104 may take pre-authorization of head-end node 102 to transmit DOCSIS requests for bandwidth to head-end node 102.

DOCSIS scheduler 504 issues grants in a MAP message that is sent to branch node 104 and then to end station 108. MAP translator 508 generates a GATE message based on the MAP message such that the time at which data from end station 108 arrives at branch node 104 is aligned with the time instance at which branch node 104 can transmit the received data to head-end node 102. The GATE message is transmitted to the branch node 108.

End station 108 transmits data at the time instance indicated by the MAP message. The branch node 104 receives the data and transmits to the head-end node 102 with minimal delay based on the time instance represented by the GATE message.

In the downstream direction, head-end node 102 receives packets from a back-end network (e.g., the internet (not shown)) and performs DOCSIS classification to determine the destination end station 108 to use and the corresponding traffic flow (for DOCSIS QoS purposes). DOCSIS scheduler 504 determines the order in which packets are transmitted in the downstream direction and the total amount of data that can be transmitted to end station 108 without exceeding the capacity of the downstream coaxial portion (branch medium 106), which may be less than the capacity of the PON (main medium 104). The DOCSIS scheduler 504 transmits the packets to the PON MAC 510 in the desired order and at the appropriate rate via the DOCSIS DS MAC 502. In this example, the downstream classification and QoS functions of EPON MAC 510 are ignored, so that the received packets are transmitted in the order selected by DOCSIS scheduler 504.

In summary, the embodiment of fig. 5 provides a way for a service provider to centralize the scheduling functions in the head-end node 102 while preserving DOCSIS protocol end-to-end, e.g., QoS and service level, protocol functionality for each end station 108, while incorporating EPON protocol into the optical portion of the network 500. The allocation made by DOCSIS scheduler 504 is converted to a corresponding allocation for EPON and transmitted to EPON branch node 104 in the appropriate format. Essentially, an EPON network is "slaved" to DOCSIS scheduler 504. Specifically, in the upstream direction, at the appropriate time, the allocation scheduled for individual end stations 108 by DOCSIS scheduler 504 in head-end node 102 is converted to an EPON allocation for the appropriate branch node 104. Branch node 104 receives transmissions from end station 108 over coaxial cables and then experiences minimal buffering delay because the allocated time slots are started on the PON immediately after arrival to continue transmitting data through branch node 104 to head end node 102.

Fig. 6 illustrates an example flow chart 600 showing steps performed by a head-end node for scheduling in a two-tier network. Flowchart 600 is described with continued reference to the example operating environment described in FIG. 5. However, the flowchart is not limited to this embodiment. Note that some of the steps shown in flowchart 600 do not necessarily have to occur in the order shown.

In step 602, a first instance in time at which an end station may transmit data to a branch node is determined. For example, DOCSIS scheduler 504 determines a first instance in time that end station 108 may transmit data to branch node 104. DOCSIS scheduler 504 generates a MAP message that allocates a first time instance to end station 108.

In step 604, a second time instance is determined at which the branch node may transmit the data received in step 602 to the head-end node. In an embodiment, the second time instance is approximately equal to the time of arrival of data from end station 108, allowing any receive processing time required by branch node 104. For example, the MAP translator 508 determines the second time instance based on the first time instance in the MAP message and based on data from the PON timebase 512. The MAP translator 508 generates a GATE message that assigns the second time instance to the branch node 104.

In step 606, the MAP message and the GATE message are transmitted. For example, head-end node 102 transmits MAP messages and GATE messages. Branch node 104 stores and processes the GATE message and forwards the MAP message to end station 108.

Fig. 7 illustrates an example flow diagram 700 showing steps performed by a branch node in a two-tier network. Flowchart 700 is described with continued reference to the example operating environment described in fig. 5. However, the flowchart is not limited to this embodiment. Note that some of the steps shown in flowchart 700 do not have to be performed in the order shown.

In step 702, a MAP message and a GATE message are received. For example, a MAP message and a GATE message are received that assigns a first instance of time to end station 108 for transmitting data. The GATE message assigns a second instance of time to branch node 104 for transmission of data received from end station 108.

In step 704, the MAP message is transmitted to the end station and the GATE message is stored and processed. For example, branch node 104 stores and processes the GATE message and forwards the MAP message to its corresponding destination end station 108. The branch node 104 prepares to transmit data received from end station 108 at approximately the second instance in time indicated in the GATE message.

In step 706, data is received from the end station at approximately the second instance in time and transmitted up to the head-end node at approximately the second instance in time allocated in the GATE message.

Example general computer System

Embodiments provided herein, or portions thereof, may be implemented in hardware, firmware, software, and/or combinations thereof.

Embodiments provided herein are applicable to any communication system between two or more devices or within a sub-component of a device. The representative functions described herein may be implemented in hardware, software, or some combination thereof. For example, one of ordinary skill in the art will appreciate based on the discussion presented herein that representative functions may be implemented using a computer processor, computer logic, application specific circuitry (ASIC), digital signal processor, or the like. Accordingly, any processor that performs the functions described herein is within the scope and spirit of the embodiments provided herein.

The following describes a general-purpose computer system that may be used to implement embodiments of the invention provided herein. The present invention can be realized in hardware or a combination of software and hardware. Thus, the present invention may be implemented in the context of a computer system or other processing system. An example of such a computer system 800 is shown in FIG. 8. Computer system 800 includes one or more processors, such as processor 804. The processor 804 may be an application specific or general purpose digital signal processor. The processor 804 is connected to a communication infrastructure 806 (e.g., a bus or network). Various software implementations of the exemplary computer system are described. After reading this description, it will become apparent to a person having ordinary skill in the relevant art how to implement the invention using other computer systems and/or computer architectures.

Computer system 800 also includes a main memory 805, preferably Random Access Memory (RAM), and may also include a secondary memory 810. The secondary memory 810 may include, for example, a hard disk drive 812 and/or a RAID array 816 and/or a removable storage drive 814, represented by a floppy disk drive, a magnetic tape drive, an optical disk drive, and the like. The removable storage drive 814 reads from and/or writes to a removable storage unit 818 by known means. Removable storage unit 818 represents a floppy disk, magnetic tape, optical disk, etc. It will be appreciated that removable storage unit 818 includes a computer usable storage medium having stored therein computer software and/or data.

In alternative implementations, secondary memory 810 may include other similar means for loading computer programs or other instructions into computer system 800. Such means may include, for example, a removable storage unit 822 and an interface 820. Examples of such means may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units 822 and interfaces 820 which allow software and data to be transferred from the removable storage unit 822 to computer system 800.

Computer system 800 may also include a communications interface 824. Communications interface 824 allows software and data to be transferred between computer system 800 and peripheral devices. Examples of communications interface 824 can include a modem, a network interface (such as an ethernet card), a communications port, a PCMCIA slot and card, etc. Software and data transferred via communications interface 824 are in the form of signals 828 which may be electrical, electromagnetic, optical or other signals capable of being received by communications interface 824. These signals 828 are provided to communications interface 824 via a communications path 826. Communication path 826 carries signals 828 and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link, and other communication channels.

The terms "computer program medium" and "computer usable medium" as used herein generally refer to media such as removable storage drive 814, a hard disk installed in hard disk drive 812, and signals 828. These computer program products are means for providing software to computer system 800.

Computer programs (or referred to as computer control logic) are stored in main memory 805 and/or secondary memory 810. Computer programs may also be received via communications interface 812. Such computer programs, when executed, enable the computer system 800 to implement the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor 804 to implement the processes of the present invention. For example, the computer program, when executed, causes the processor 804 to implement a portion or all of the steps described above with reference to the flow diagrams herein. Where the invention is implemented using software, the software may be stored in a computer program product and loaded into computer system 800 using RAID array 816, removable storage drive 814, hard disk drive 812 or communications interface 824.

In other embodiments, features of the invention are implemented primarily in hardware using hardware components such as Application Specific Integrated Circuits (ASICs) and programmable or static gate arrays. Implementation of a hardware state machine to perform the functions described herein will also be apparent to those skilled in the relevant art.

Conclusion

While various embodiments have been described above, it should be understood that they have been presented by way of example, and not limitation. It will be apparent to persons skilled in the relevant art that various changes in form and detail can be made therein without departing from the spirit and scope of the embodiments provided herein.

The embodiments presented herein have been described above with the aid of functional building blocks and method steps illustrating the performance of specific functions and relationships thereof. The boundaries of these functional building blocks and method steps have been arbitrarily defined herein for the convenience of the description. Alternate boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Accordingly, any such alternate boundaries are within the scope and spirit of the claimed embodiments. Those skilled in the art will appreciate that these functional building blocks may be implemented by discrete components, application specific integrated circuits, processors executing appropriate software, etc., or any combination thereof. Thus, the breadth and scope of an embodiment of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

Claims (10)

1. A head-end node for scheduling uplink transmission times in a two-tier network, comprising:

a scheduler configured to generate a first message to allocate bandwidth and a first time instance for an end station to transmit data to a branch node via a branch medium of the two-tier network;

a message converter coupled to the scheduler and configured to determine a second time instance of arrival of data from the end station at the branch node and generate a second message granting the branch node bandwidth to transmit data received from the end station at the second time instance to the head-end node over a backbone medium of the two-tier network.

2. The head-end node of claim 1, wherein the scheduler is a cable data service interface specification scheduler, the end station is a cable modem, the first message is a MAP message, the second message is a GATE message, the backbone medium of the dual-tier network is an optical medium, and the branch medium of the dual-tier network is a coaxial cable medium.

3. The head-end node of claim 1, wherein the scheduler is configured to receive bandwidth requests from the branch nodes, wherein the requests originate from the end stations coupled to the branch nodes over the branch medium.

4. The headend node of claim 1, wherein the scheduler determines the first instance in time and an amount of bandwidth to allocate to the end stations based on a quality of service and a service level agreement associated with the end stations.

5. The head-end node of claim 1, further comprising a time base coupled to the scheduler, the scheduler configured to determine the first time instance based on data received from the time base.

6. The head-end node of claim 1, further comprising a time base coupled to a MAP converter, the MAP converter configured to determine the second time instance based on data from the time base.

7. The head-end node of claim 2, further comprising a passive optical network physical layer for transmitting the MAP message and the GATE message, wherein the branch node stores and processes the GATE message and forwards the MAP message to the cable modem.

8. A branching node, comprising:

a first downstream physical layer configured to receive a first message and a second message from a head-end node; and

a second downstream physical layer coupled to the first downstream physical layer and configured to transmit the first message to a terminal station;

wherein the first message specifies a first instance in time at which the end station transmits data to the branch node and an amount of data that the end station is capable of transmitting; and is

Wherein the second message specifies a second instance in time at which the branch node transmits data received from the end station to the head-end node, wherein the second instance in time is approximately equal to the time at which the branch node receives the data from the end station.

9. The branch node of claim 8, wherein the first downstream physical layer is a passive optical network downstream physical layer, the second downstream physical layer is a cable data service interface specification physical layer, the first message is a MAP message, the second message is a GATE message, the end stations are cable modems, and the head-end node comprises a cable modem termination system.

10. A method for scheduling uplink transmission time in a dual-tier network, comprising:

generating a first message to allocate bandwidth and a first time instance to a first device to transmit data to a branch node;

determining a second time instance of arrival of the data from the first device at the branch node; and

generating a second message granting the branch node bandwidth to transmit the data received by the first device at the second time instance to a head-end node.