Frame relay over point to multipoint links

[0001] The present invention relates to data communication networks and more particularly to systems and methods for adapting Frame Relay networking techniques to new physical layer access technologies.

[0002] Frame Relay is a packet-based scheme for implementing a wide area network (WAN). Frame Relay information is divided into packets or frames. Frame Relay packets travel through a series of Frame Relay switches between a source node and a destination node. Frame Relay employs a very simple routing scheme. Packets are sent via a virtual circuit between the origin and destination. All packets of the same virtual circuit follow the same preconfigured route through a Frame Relay network.

[0003] Although Frame Relay lacks the flexibility inherent in Internet Protocol (IP) based routing schemes, it is relatively simple to implement and also provides many qualities of service features. Furthermore, because Frame Relay packets may encapsulate IP packets, Frame Relay may be used to support IP-based applications such as web access and e-mail.

[0004] Typical Frame Relay networks use point to point links to implement network connections both between intermediate nodes and to provide access to users at the network edges. These point to point links are often T-1 or T-3 connections.

[0005] Increasingly, however, broadband access is provided to businesses and residences by the use of point to multipoint networks where a central access node communicates with many subscriber nodes via a shared transmission medium. One example of such a point to multipoint network is a data over cable network where numerous cable modems exchange data with a head end. Another example of a point to multipoint network is a broadband wireless access network where numerous subscriber radios exchange data with a central access point.

[0006] It would be desirable to provide Frame Relay services to users of such point to multipoint networks. One could then obtain easier access to the existing Frame Relay infrastructure and the services provided thereon. Unfortunately, Frame Relay packets cannot traverse point to multipoint networks as they are currently configured. What is needed are systems and methods for adapting Frame Relay services to point to multipoint networks and providing Frame Relay connectivity via such networks.

[0007] Frame Relay connectivity is provided via point to multipoint networks by virtue of one embodiment of the present invention. Frame Relay access can thus be readily provided via point to multipoint networks such as data over cable networks and wireless networks. The end user obtains Frame Relay quality-of-service features via the point to multipoint network. The network service provider gains an additional method of access to the Frame Relay wide area network (WAN). In one embodiment, Frame Relay quality of service information is translated into parameters appropriate for use with point to multipoint protocols so that point to multipoint network bandwidth is properly managed.

[0008] According to one aspect of the present invention, a method providing Frame Relay services via a multipoint network includes: receiving a point to multipoint protocol packet at a central access node of the point to multipoint network, extracting a Frame Relay packet from the point to multipoint protocol packet at the central access node, and forwarding the Frame Relay packet via a Frame Relay network.

[0009] A further understanding of the nature and advantages of the invention herein may be realized by reference to the remaining portions of the specification and the attached drawings.

[0016] One embodiment of the present invention provides Frame Relay services via a point to multipoint network. The point to multipoint network can provide the network user so-called “last mile” access for Frame Relay services. FIG. 1 depicts a network architecture for providing Frame Relay services in this way. A point to multipoint network 102 interconnects a central access point 104 and multiple subscriber units 106. One exemplary implementation of point to multipoint network 102 would be a data over cable network where central access point 104 is equipped with a data over cable head end and each of subscriber units 106 exploits a cable modem.

[0017] Point to multipoint network 102 is implemented in the physical layer by a shared transmission medium, e.g., coaxial cable. Point to multipoint network 102 may then, e.g., operate in accordance with a point to multipoint protocol such as the DOCSIS 1.0 specifications or DOCSIS 1.1 specifications published by Cable Television Laboratories, Inc. of Louisville, Colo. The entire contents of these DOCSIS specifications are incorporated herein by reference for all purposes.

[0018] Another implementation of point to multipoint network 102 is a wireless network. In one such implementation, the media access control (MAC) layer is handled according to the DOCSIS protocol while the physical layer uses an OFDM-based modulation technique. One example of an OFDM modulation technique is VOFDM, a wireless communication standard maintained by the Broadband Wireless Internet Forum (BWIF).

[0019] A central access point 104 interfaces between point to multipoint network 102 and a Frame Relay network 108. Frame Relay network 108 operates according to Frame Relay protocols as established by the Frame Relay Forum of Fremont, Calif. and the International Telecommunications Union (ITU) of Geneva, Switzerland. Specifications describing Frame Relay operation include the FRF 1.2 User to Network Implementation Agreement (available from the Frame Relay Forum); ITU Recommendations Q.922 and Q.933 (available from the ITU). All of these documents are incorporated herein by reference in their entirety for all purposes.

[0020] Data travels via Frame Relay network 108 between central access point 104 and many possible destination nodes at the edges of Frame Relay network 108. One example of such a destination is shown, a Frame Relay end point 110. Traffic through Frame Relay network 108 travels via intermediate nodes known as Frame Relay switches. According to the present invention, Frame Relay services are provided to subscriber units 106. Subscriber units 106 can effectively act as a part of Frame Relay network 108.

[0021] FIG. 2 depicts a network processing system 200 that can be used to implement any of the elements depicted in FIG. 1 or individual nodes of Frame Relay network 108. In one embodiment, network processing system 200 is a programmable machine that may be implemented in hardware, software, or any combination thereof. A processor 202 executes codes stored in a program memory 204. Program memory 204 is one example of a computer readable storage medium. Program memory 204 can be a volatile memory. Another form of computer-readable storage medium storing the same codes would be some type of non-volatile storage such as floppy disks, CD ROMs, DVD ROMs, hard disks, flash memory, etc. A carrier wave that carries the code across a network is another example of a computer-readable storage medium.

[0022] Network processing system 200 interfaces with physical media via a plurality of network interfaces 206. For example, one of network interfaces 206 may couple to a point to multipoint network such as a data over cable network or wireless network. Alternatively, one of network interfaces 206 may couple to a point to point link that carries Frame Relay traffic. Other examples of network interfaces include Ethernet interfaces, DSL interfaces, Token Ring interfaces, Fast Ethernet interfaces, Gigabit Ethernet interfaces, ATM interfaces, HSSI interfaces, POS interfaces, FDDI interfaces, etc. As packets are received, processed, and forwarded by network processor system 200, they are stored in a packet memory 208.

[0023] Network processing system 200 may be an Internet Protocol router and may include an operating system such as the Internetwork Operating System (IOS®) of Cisco Systems, Inc. and any appropriate application software. In one embodiment, central access point 104 is implemented as a router of the UBR7200 series available from Cisco Systems. Also, one or more of subscriber units 106 can be implemented as a 3600 series or 2600 series router, also both available from Cisco Systems. The architecture depicted in FIG. 2 is merely representative.

[0024] FIG. 3 depicts protocol stacks used for communication among the various elements depicted in FIG. 1. The stacks in FIG. 3 assume that Frame Relay connectivity is used to transfer IP packets. In this way, internet services such as web browsing and email can be provided by the Frame Relay connectivity that it is implemented over the point to multipoint network. A first protocol stack 302 is used for communication between subscriber unit 106 and a personal computer or other customer premise equipment (CPE) located at the subscriber location. Typically, IP packets will be encapsulated within Ethernet frames for communication at the CPE side of the subscriber unit. Therefore, protocol stack 302 shows an IP layer above an Ethernet layer.

[0025] A second protocol stack 304 is used for communication between subscriber unit 106 and central access point 104. For communication between subscriber unit 106 and central access point 104, an appropriate point to multipoint protocol is used. Each subscriber unit 106 includes both the Frame Relay client and a DOCSIS client to implement the respective protocols. A modified DOCSIS client or other substitute point to multipoint client may substitute for the DOCSIS client.

[0026] Subscriber unit 106 extracts IP frames to be forwarded via Frame Relay services from the Ethernet frames and then encapsulates these IP packets within Frame Relay packets. Subscriber unit 106 then encapsulates the Frame Relay packets within DOCSIS packets.

[0027] In one embodiment, encapsulating the Frame Relay packet within a DOCSIS packet includes first encapsulating the Frame Relay packet within an Ethernet packet and then encapsulating the Ethernet packet within the DOCSIS packet. The Ethernet packet structure is exploited because it is recognized as suitable packet content by the existing DOCSIS protocol but there is no invocation of Ethernet protocol software.

[0028] Once received at central access point 104, the Frame Relay information is extracted from the DOCSIS or other point to multipoint protocol packets. Thus, protocol stack 304 includes a DOCSIS layer as the lowest layer, a Frame Relay layer above the DOCSIS layer and an IP layer above the DOCSIS layer. Any point to multipoint protocol may substitute for DOCSIS or the physical layer of DOCSIS may be replaced by another point to multipoint protocol or a modified version of DOCSIS.

[0029] A third protocol stack 306 shows the interactions between central access point 104 and Frame Relay end point 110 via Frame Relay network 108. Central access point 304 extracts the Frame Relay packet from the DOCSIS packet. The Frame Relay information is then forwarded through Frame Relay network 108 in accordance with Frame Relay protocols. Frame Relay endpoint 110 then retrieve the IP information from the Frame Relay packets. To support this type of communication, central access point 104 and Frame Relay endpoint 110 incorporate protocol stack 306 which includes an IP layer above a Frame Relay layer.

[0030] The protocol stacks have been described with reference to generating Frame Relay packets at subscriber unit 106 and forwarding Frame Relay packets to end point 110. It will be appreciated that a reverse process will be followed to transfer Frame Relay information in the other direction. An Internet Protocol packet is encapsulated within a Frame Relay packet at Frame Relay endpoint 110. Frame relay endpoint 110 forwards this packet across Frame Relay network 108 to central access point 104.

[0031] Central access point 104 encapsulates the Frame Relay packet within a DOCSIS packet. This DOCSIS packet will then be forwarded to one of subscriber units 106 via point to multipoint network 102. At the particular subscriber unit 106, the Frame Relay packet is extracted from the DOCSIS packet and the IP packet is extracted from the Frame Relay packet. This subscriber unit 106 can then encapsulate the IP packet within an Ethernet packet for forwarding to a collocated CPE device such as a PC.

[0032] FIG. 4 depicts packet structures used in forwarding Frame Relay information across a point to multipoint network in accordance with one embodiment of the present invention. As has been discussed, in one embodiment, the point to multipoint network of FIG. 1 uses the DOCSIS protocol. The header portion of DOCSIS packets includes a code point that specifies the contents of the packet. In the current version of the DOCSIS specifications, there is no code point that designates Frame Relay contents.

[0033] A first packet structure 402 assumes modification of the DOCSIS protocol to allow for a code point that specifies Frame Relay contents. The header includes this code point and the Frame Relay packet is in the payload portion of the DOCSIS packet. A second packet structure 404 requires no such modification to the DOCSIS protocol. In this packet structure, the DOCSIS header includes the code point that designates the DOCSIS packet payload as an ethernet packet. Such a codepoint is already defined in the DOCSIS specifications. The Frame Relay packet is then included within an Ethernet packet where a header of the ethernet packet includes a code point designating the Ethernet packet cargo as being Frame Relay information. This structure requires extra overhead but does not require modification to the DOCSIS protocol. The use of this Ethernet packet is for the purpose of facilitating encapsulation of Frame Relay information and does not imply use of an Ethernet type physical layer or MAC layer in implementing point to multipoint network 102.

[0034] At both central access point 104 and subscriber unit 106 there is interaction between clients implementing the Frame Relay and point to multipoint protocols. FIG. 5 shows the interaction among these clients in accordance with one embodiment of the present invention. A Frame Relay client 502 interacts with a DOCSIS client 504 via DOCSIS/Frame Relay interface client 506. Interface client 506 performs encapsulation and de-encapsulation as described above to support carrying Frame Relay information across point to multipoint network 102. The clients of FIG. 5 may be installed in a DOCSIS network interface at either central access point 104 or subscriber unit 106.

[0035] Furthermore, at central access point 104, interface client 506 assures that Frame Relay quality of service requirements are implemented through point to multipoint network 102. The quality of Frame Relay service given to a particular subscriber is governed by a service level agreement (SLA) between the subscriber and the Frame Relay service provider. According to one embodiment of the present invention, such service level agreements may be maintained with users of subscriber units 106.

[0036] A level of service guaranteed to a particular subscriber is defined by various parameters of a so-called “virtual circuit” between the subscriber and a representative Frame Relay endpoint such as Frame Relay endpoint 110. A virtual circuit is a two-way defined data path between two nodes of a Frame Relay network. In the context of the system of FIG. 1, a virtual circuit may, e.g., interconnect one of subscriber units 106 and frame relay end point 110. A frame relay packet to be sent along the virtual circuit is identified by a data link connection identifier (DLCI) in the packet header. Frame relay switching devices use the DLCI to determine where to forward individual packets.

[0037] There are various virtual circuit parameters that are used to manage quality of service and define the obligations of the Frame Relay service provider. One such parameter is the committed information rate (CIR). The CIR is the average information carrying capacity of the virtual circuit in bits per second. The CIR is averaged over a time interval having duration T_c. Another parameter, the committed burst size, B_c, is a measure of the maximum amount of data in bits that the service provider commits to transfer during any interval of duration T_c. Another parameter, excess burst size B_e, represents the maximum amount of data in bits in excess in excess of B_c that a Frame Relay network can attempt to deliver during duration T_c. Data in excess of B_c but below B_e may be discarded if no capacity is available.

[0038] Before creating or modifying a virtual circuit that traverses point to multipoint network 102, interface client 506 assures that the Frame Relay traffic parameters of the new or modified virtual circuit can be accommodated within the available DOCSIS bandwidth. Interface client 506 assesses the impact of a new or modified virtual circuit by computing the values of DOCSIS traffic parameters that would result from the aggregate of all virtual circuits making use of a DOCSIS connection. DOCSIS manages upstream (subscriber unit to central access point) traffic separately from downstream (central access point to subscriber unit) so the impact of Frame Relay traffic modification on both directions is considered.

[0039] Upstream DOCSIS traffic parameters are computed for each DOCSIS subscriber identifier (SID). There may be multiple SIDs per subscriber unit. The available DOCSIS bandwidth for a given SID is determined by DOCSIS committed information rate (CIR_DOCSIS), peak rate DOCSIS traffic (peakrateupstream_DOCSIS) and a maximum DOCSIS burst size (burst_DOCSIS). The CIR_DOCSIS value represents the average number of bits per unit time T_c-DOCSIS that can travel between a given subscriber unit 106 and central access point 104 via point to multipoint network 102. The peakrateupstream_DOCSIS value indicates the maximum information rate that point to multipoint network 102 will attempt to provide upstream for a given SID. The burst_DOCSIS value is a measure of the amount of data in excess of the CIR_DOCSIS value that point to multipoint network 102 will provide for a given subscriber unit 106.

[0040] For downstream DOCSIS traffic, there is only one relevant traffic parameter, peakratedownstream_DOCSIS. This is for the cumulative downstream traffic handled by a given head end DOCSIS network interface. The upstream and downstream DOCSIS parameters are maintained by a DOCSIS bandwidth manager within DOCSIS client 504.

[0041] FIG. 6 is a flow chart describing steps performed by interface client 506 at central access point 104 in adding or modifying a virtual circuit that will traverse point to multipoint network 102. At step 602, interface client 506 receives a request to add or modify a Frame Relay virtual circuit and adjust DOCSIS quality of service parameters accordingly. The request includes the Frame Relay CIR, T_c and B_e values. The parameter B_c is by definition equivalent to T_c/CIR. Interface client 506 determines the impact on the available DOCSIS bandwidth between central access point 104 and subscriber unit 106. When a virtual circuit is either created or modified, the DOCSIS bandwidth manager first checks if it is possible to accommodate the extra bandwidth required by the virtual circuit and then allocate the necessary bandwidth if it is in fact available.

[0042] At step 604, interface client 506 determines the DOCSIS upstream committed information rate, CIR_DOCSIS that would result from fulfilling the request of step 602. This is computed by

[0043] ${\mathrm{CIR}}_{\mathrm{DOCSIS}}=\sum _{\mathrm{dlci}}\left(\mathrm{CIR}\right)$
which sums the committed information rates of the all the virtual circuits carried over a given DOCSIS SID including the one to be created or modified. Then at step 606, Frame Relay interface client 506 computes the projected DOCSIS upstream excess burst size, burst_DOCSIS according to

[0044] ${\mathrm{Burst}}_{\mathrm{DOCSIS}}=\sum _{\mathrm{dlci}}\left(\frac{b_e}{T_c}\right).$
This formula sums all of the Frame Relay virtual circuit excess burst sizes for a given SID. Then at step 608, the DOCSIS upstream peakrate is computed as peakrateupstream_DOCSIS=CIR_DOCSIS+Burst_DOCSIS. This completes the computations for the upstream DOCSIS bandwidth.

[0045] The only computation for the downstream DOCSIS bandwidth is peakratedownstream_DOCSIS=CIR_DOCSIS+Burst_DOCSIS. This computation totals all of the Frame Relay virtual circuits managed through a given DOCSIS network interface at the head end.

[0046] After step 610, interface client 506 has a complete picture of the DOCSIS bandwidth management impact of the requested virtual circuit creation or modification. At step 612, interface client 506 determines if the necessary DOCSIS bandwidth is available by passing the computed DOCSIS bandwidth parameters to the bandwidth manager within DOCSIS client 504. If the DOCSIS bandwidth approves these new DOCSIS management parameters, the bandwidth is available.

[0047] If the bandwidth is available, interface client 506 accepts the request of step 602 at step 614 by sending a request acknowledgement to Frame Relay client 502 and notifying DOCSIS client 504 that the new bandwidth will in fact be used. The bandwidth manager within DOCSIS client 504 updates the various DOCSIS traffic management parameters appropriately. At step 616, Frame Relay client 502 sets up the new virtual circuit that traverses point to multipoint network 102. On the other hand, if step 612 determines that insufficient DOCSIS bandwidth is available, then interface client 506 rejects the request and notifies Frame Relay client 502 accordingly at step 618.

[0048] It is understood that the examples and embodiments described herein are for illustrative purposes only and that various modifications and changes in light thereof will be apparent to persons skilled in the art and are to be included within the spirit and purview of this application and the scope of the appended claims and their full scope of equivalents.