Source: http://www.google.com/patents/US7577163?dq=5787449
Timestamp: 2015-03-02 13:26:15
Document Index: 580141314

Matched Legal Cases: ['Application No. 60', 'art.\n1', 'art. 4', 'art. 2', 'art. 4', 'art 3']

Patent US7577163 - Apparatus and method for facilitating data packet transportation - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsEmbodiments of the present invention described and shown in the specification and drawings facilitate data packet transportation. One aspect of the invention multiplexes time-sensitive TDM (Time Division Multiplexed) and other synchronous data, and asynchronous data traffic, onto a communication channel...http://www.google.com/patents/US7577163?utm_source=gb-gplus-sharePatent US7577163 - Apparatus and method for facilitating data packet transportationAdvanced Patent SearchPublication numberUS7577163 B2Publication typeGrantApplication numberUS 11/469,664Publication dateAug 18, 2009Filing dateSep 1, 2006Priority dateAug 24, 2000Fee statusPaidAlso published asUS7103063, US20020027928, US20070064722, WO2002017552A1Publication number11469664, 469664, US 7577163 B2, US 7577163B2, US-B2-7577163, US7577163 B2, US7577163B2InventorsRong C. FangOriginal AssigneeTellabs Reston, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (23), Non-Patent Citations (4), Referenced by (2), Classifications (17), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetApparatus and method for facilitating data packet transportation
US 7577163 B2Abstract
Embodiments of the present invention described and shown in the specification and drawings facilitate data packet transportation. One aspect of the invention multiplexes time-sensitive TDM (Time Division Multiplexed) and other synchronous data, and asynchronous data traffic, onto a communication channel in a manner that minimizes jitter in the delivery of the TDM data traffic while efficiently transporting asynchronous data traffic. Another aspect of the invention provides dynamic bandwidth sharing on a communication ring. The dynamic bandwidth sharing aspect of the present invention facilitates the efficient utilization of bandwidth of communication rings, particularly in those rings that cover large geographic areas.
1. A system for receiving packets, comprising:
an asynchronous data packet receiver;
a time division multiplex packet receiver;
a frame synchronization packet receiver;
a fan out circuit operable to receive a bit stream of data, the fan out circuit operable to provide the bit stream of data to the asynchronous data packet receiver, the time division multiplex packet receiver, and the frame synchronization packet receiver;
wherein the frame synchronization packet processor is operable to identify a frame code in the bit stream of data for a frame of data, the frame synchronization packet receiver operable to process frame synchronization packets of the frame in the bit stream of data in response to identification of the frame code, the frame synchronization packet receiver operable to transfer operational control to the time division multiplex packet receiver;
wherein the time division multiplex packet receiver is operable to process time division multiplex packets of the frame upon receiving control from the frame synchronization packet receiver, the frame synchronization packet receiver operable to transfer operational control to the asynchronous data packet receiver upon receipt of all time division multiplex packets of the frame in the bit stream of data by the time division multiplex receiver;
wherein the asynchronous data packet receiver is operable to process asynchronous data packets of the frame upon receiving control from the frame synchronization packet receiver, the frame synchronization packet receiver operable to receive operational control from the asynchronous data packet receiver upon receipt of all asynchronous data packets of the frame in the bit stream of data by the asynchronous data packet receiver.
2. The system of claim 1, wherein the time division multiplex packet receiver returns operational control to the frame synchronization packet receiver upon receiving an individual time division multiplex packet.
3. The system of claim 2, wherein the frame synchronization packet receiver is operable to pass operational control to the time division multiplex packet receiver for each time division multiplex packet in the frame.
4. The system of claim 1, wherein the asynchronous data packet receiver processes each remaining byte received of the frame in the bit stream of data after the last time division multiplex packet is processed.
5. The system of claim 4, wherein the asynchronous data packet receiver is operable to determine whether any initial bytes received in the frame are part of a packet with other bytes received from a previous frame.
6. A system for transmitting packets, comprising:
an input processor operable to receive frame synchronization packets, time division multiplex packets, and asynchronous packets;
a shared memory operable to store packets received by the input processor according to packet type and priority;
a directory operable to store pointers to packets placed into the shared memory;
a directory processor operable to identify a pointer for a next packet to be transmitted in accordance with a frame synchronization signal; and
an output processor operable to transport a frame of packets from the shared memory onto a communication channel according to pointers identified by the directory processor, wherein the frame is associated with the frame synchronization signal; and
wherein each pointer includes a length of an associated packet, a location in the shared memory of the associated packet, and a priority of the associated packet.
a communication register operable to store the pointer of the next packet identified by the directory processor.
8. The system of claim 6, wherein the directory processor removes an identified pointer from the directory.
9. The system of claim 6, wherein the shared memory stores time division multiplex packets in a dedicated memory area for easy access thereto.
10. The system of claim 9, wherein a size of the dedicated memory area is dynamically assigned.
a partial packet counter operable to identify partial payloads of asynchronous data packets not transmitted within a particular frame.
12. The system of claim 6, wherein the input processor is operable to discard packets in response to insufficient storage space within the shared memory.
13. The system of claim 6, wherein the directory organizes pointers by priority.
14. A system for transmitting packets, comprising:
a directory processor operable to identify a pointer for a next packet to be transmitted in accordance with a frame synchronization signal;
an output processor operable to transport a frame of packets from the shared memory onto a communication channel according to pointers identified by the directory processor, wherein the frame is associated with the frame synchronization signal;
an asynchronous data packet generator operable to generate asynchronous data packets;
a time division multiplex packet generator operable to generate time division multiplex data packets;
a frame synchronization packet generator operable to generate frame synchronization data packets; and
wherein the frame synchronization packet generator is operable to successively enable packet generation by the time division multiplex packet generator and then the asynchronous data packet generator upon generation of a frame synchronization packet.
15. A system for processing communication traffic, comprising:
a traffic identification unit operable to receive traffic from one or more ports, the traffic identification unit operable to classify and prioritize the traffic;
a traffic policing unit operable to police the traffic according to respective classification and priorities, the traffic policing unit including a plurality of policing devices operable to receive the traffic as determined by the traffic identification unit, the traffic policing unit operable to distinguish subscription traffic from over-subscription traffic;
a scheduler operable to separately store subscription traffic and over-subscription traffic for subsequent transport on a communication link in accordance with subscription bandwidth assigned thereto and over-subscription bandwidth shared among other nodes on the communication link, the scheduler sending out subscription traffic over the link with priority over over-subscription traffic.
16. The system of claim 15, wherein subscription traffic having a constant bit rate and a variable bit rate with normal burst size, over-subscription traffic having a variable bit rate with excess burst and an unspecified bit rate.
17. The system of claim 15, wherein the scheduler includes a memory operable to store the traffic and a packet multiplexer operable to place subscription traffic stored in the memory onto the communication link.
18. The system of claim 17, wherein the memory includes a plurality of committed buffers each associated with a respective input port, the packet multiplexer operable to access the plurality of committed buffers in a round robin fashion to place the subscription traffic onto the communication link.
19. The system of claim 15, wherein the scheduler includes:
a memory operable to store the traffic;
and a ring access controller operable to place the over-subscription traffic stored in the memory onto the communication link.
20. The system of claim 19, wherein the memory includes a plurality of over-subscription buffers, the scheduler operable to place the over-subscription traffic into an appropriate over-subscription buffer according to the class and priority of the over-subscription traffic.
21. The system of claim 20, wherein the ring access controller is operable to place over-subscription traffic onto the communication link according to an over-subscription bandwidth assigned to the scheduler, the ring access controller accessing the over-subscription buffers according to a pre-determined rate assigned to each over-subscription buffer, the ring access controller only accessing certain over-subscription buffers based on the associated class and priority upon being constrained by the over-subscription bandwidth.
22. The system of claim 19, wherein the ring access controller is operable to generate a congestion signal in response to determining congestion associated with the over-subscription traffic, the ring access controller operable to receive a congestion signal generated by another node in the system.
23. The system of claim 22, wherein the ring access controller is operable to adjust the bandwidth associated with the scheduler in response to any congestion signal.
24. The system of claim 22, wherein the ring access controller is operable to generate a congestion clear signal in response to determining congestion is no longer associated with the over-subscription traffic, the ring access controller operable to receive a congestion clear signal generated by another node in the system.
25. The system of claim 24, wherein the ring access controller is operable to adjust the bandwidth associated with the scheduler in response to any congestion clear signal. Description
This application is a continuation application of U.S. application Ser. No. 09/935,781 filed Aug. 24, 2001 and now U.S. Pat. No. 7,103,063 issuing on Sep. 5, 2006 which claims priority under to U.S. Provisional Application No. 60/227,521 filed Aug. 24, 2000, each of which is hereby incorporated herein by reference.
Some embodiments of the present invention inject a timing synchronization signal into a communication channel to facilitate the minimization of jitter and the transportation of asynchronous data, and to simplify the multiplexing and demultiplexing of synchronous data. The timing synchronization signal is injected into the data stream on the communication channel at fixed time intervals and is used to regulate the timing of all synchronous data, including Time Division Multiplex data (�TDM�), and asynchronous data transportation on the channel. In some embodiments, the timing synchronization signal is carried in a fixed-length frame synch packet with a unique frame code that is transported unscrambled in order to reduce the time needed to re-synchronize to the timing synchronization signal.
Some embodiments of the present invention, related to communication rings, assign a baseline amount of bandwidth (the �subscription� bandwidth) and an Acceptable Over-Subscription Bandwidth to each communication node on a communication ring. The maximum amount of ring bandwidth that a node is permitted to use at any particular time, in addition to the node's baseline subscription bandwidth, is the node's Access Bandwidth. The actual ring bandwidth available to a node at any particular time, in addition to the node's baseline subscription bandwidth, is the node's actual Over-Subscription Bandwidth. For each node, if the amount of over-subscription bandwidth available on the ring is less than the Acceptable Over-Subscription Bandwidth and the node's over-subscription traffic that is ready to be sent to the ring requires more than the node's actual Over-Subscription Bandwidth, then an access congestion indication will be sent to the rest of the nodes on the ring.
FIG. 1 is a diagram depicting an embodiment of the present invention for facilitating data packet transportation;
FIG. 2 is a timing diagram depicting an embodiment of the present invention for multiplexing synchronous and asynchronous data onto a communication channel;
FIG. 3 is a block diagram depicting an embodiment of a Trunk Transmitter and Receiver of the present invention;
FIG. 4 is a diagram depicting an embodiment of a Frame Synchronization Packet format of the present invention;
FIG. 5 is a diagram depicting an embodiment of a TDM Packet format of the present invention;
FIG. 6 is a diagram depicting an embodiment of an Asynchronous Data Packet format of the present invention;
FIG. 7 is a block diagram depicting the reception, decoding, and processing of packets in an embodiment of the present invention;
FIG. 8 is a flow chart depicting the operation of a Data Packet Processor in an embodiment of the present invention;
FIG. 9 is a block diagram depicting an embodiment of a Trunk Transmitter of the present invention;
FIG. 10 is a diagram depicting a embodiment of the implementation of a Pointer Directory of the present invention;
FIG. 11 is a diagram depicting the relationship between the Pointer Directory and Shared Memory in an embodiment of the present invention;
FIG. 12 is a flow chart depicting the operation of an Input Processor in an embodiment of the present invention;
FIG. 13 is a flow chart depicting the operation of a Directory Processor in an embodiment of the present invention;
FIG. 14 is a flow chart depicting the operation of an Output Processor in an embodiment of the present invention;
FIG. 15 is a diagram depicting an embodiment of the aspect of the present invention for dynamic bandwidth sharing on a communication ring where the ring bandwidth is divided into two categories;
FIG. 16 is a diagram depicting the processing of traffic within a node in preparation for the insertion of the traffic onto a communication ring;
FIG. 17 is a diagram depicting an embodiment of the present invention for processing traffic within a node in preparation for the insertion of the traffic onto a communication ring;
FIG. 18 is a block diagram depicting an embodiment of the present invention for processing traffic within a node in preparation for the insertion of the traffic onto a communication ring;
FIG. 19 is a table depicting an embodiment of a traffic identification table of the present invention for use in Stage 1 processing;
FIG. 20 is a block diagram depicting an embodiment of the present invention for conducting Stage 2 processing;
FIG. 21 is a block diagram depicting an embodiment of the present invention for conducting Stage 3 processing on committed (also referred to as subscription) traffic;
FIG. 22 is a block diagram depicting an embodiment of the present invention for conducting Stage 3 processing on over-subscription traffic;
FIG. 23 is a block diagram depicting the use of a weighted fair scheduler in an embodiment of the present invention for dynamic congestion control;
�Computer system� refers to individual standalone computers, multiple computers coupled in any manner, and software simulations of computers regardless of the intended use of the computer system or the technology used to implement the computer system. The term �Computer system� includes, but is not limited to, packet-switching systems and other communication switching systems.
�Frame Cycle� refers to the time period on a communication channel beginning with the start of the transmission of a Frame Synchronization Packet and ending with the start of the transmission of the next subsequent Frame Synchronization Packet on that communication channel. In some embodiments of the present invention depicted in FIG. 2, Communication Channel 201 transports a sequence of data packets, where the data packets are depicted as traveling from right to left through Communication Channel 201, starting with Frame Synchronization Packet 210 and continuing with TDM Packets 215 and Asynchronous Data Packet 220. The sequence then repeats, starting again with Frame Synchronization Packet 210. Frame Cycle 205 begins at the start of Frame Synchronization Packet 210 and ends at the start of the next subsequent Frame Synchronization Packet 210. As is known in the art, if Communication Channel 201 transports data at a particular bit rate, for example, 56,000 bits per second (�56 kbps�), then a known number of bits can be transported during a Frame Cycle 205. For example, at a bit rate of 56 kbps and a Frame Cycle 205 duration of one millisecond, 56 bits (or 7 bytes, given that eight bits equal one byte) can be transported during Frame Cycle 205. In some embodiments, during particular frame cycles, no synchronous data may be available for transport and thus no TDM Packets would be transported during such a frame cycle. Similarly, in some embodiments and during particular frame cycles, no asynchronous data may be available for transport and thus no Asynchronous Data Packets would be transported during such a frame cycle.
�Frame Synchronization Packet� refers to a data packet of the present invention for identifying the start of a Frame Cycle. The Frame Synchronization Packet may also be used to transport Operation, Administration, and Maintenance (OAM) data as is known in the art. FIG. 4 depicts an embodiment of the format of a Frame Synchronization Packet. In some embodiments, the Frame Synchronization Packet starts with a unique frame code, composed of two bytes, F1 401 and F2 402, for identifying the beginning of a Frame Cycle. The length of the packet is fixed. In the embodiment depicted in FIG. 4, the payload length, which does not include the frame code, is 14 bytes. As is known in the art, other payload lengths may be employed. Frame code bytes F1 401 and F2 402 are framing bytes that indicate the beginning of a frame, e.g. a 125 microsecond (us) frame. F1 401 and F2 402 are not scrambled, but the rest of bytes in the Frame Synchronization Packet are scrambled in some embodiments for increased efficiency as is known in the art. The pattern of F1 401 and F2 402 shown in FIG. 4 is an example and other patterns may be used as are known in the art. In the embodiment depicted in FIG. 4, Byte-1 403 and Byte-2 404 indicate the number of bytes directly following this Frame Synchronization Packet that will be occupied by TDM Packets on the communication channel transporting the Frame Synchronization Packet. In some embodiments, this number is calculated from the number of TDM Packets provisioned on the communication channel during service provisioning time as is known in the art. In other embodiments, the number of bytes that will be occupied by TDM Packets is calculated from the TDM Packets that are actually queued for transport on the communication channel following the Frame Synchronization Packet. Other methods for calculating the number of bytes, as are known in the art, may also be employed. In the preferred embodiment depicted in FIG. 4, Byte-3 405 and Byte-4 406 indicate the failed nodes on a 16-node ring comprising the communication channel as is known in the art. Byte-3 405 and Byte-4 406 may be used for other purposes as are known in the art. In this embodiment, the rest of the packet is used for OAMP (Operation, Administration, Maintenance, and Provisioning) bytes 407, including a check sum for the payload as is known in the art.
�TDM Packet� refers to a data packet of the present invention for transporting TDM traffic. FIG. 5 depicts an embodiment of the format of a TDM packet. The depicted TDM packet has two overhead bytes (Byte-1 501 and Byte-2 502), and fixed length TDM payload 503 whose length depends on the type of TDM traffic to be carried. In some embodiments, Byte-1 501 is a service identification byte used to indicate the type of TDM traffic carried by the packet, e.g. DSl, VTl, DS3, STSl, or STSn, as are known in the art. In some embodiments, Byte-2 502 contains OAMP messages for the traffic carried in TDM payload 503, as is known in the art. When Byte-1 501 is a service identification byte, and the length of the Frame Cycle is known, the length of the TDM payload is determined as is known in the art. For example, in a 125 us Frame Cycle:
For 64 Kilobits per second (Kb/s): 1 byte For 384 Kb/s: 6 bytes For DSl: 24 bytes with the 193rd bit stored in Byte 2 (in some embodiments) For DS3/STS 1: 810 bytes For STSn: n�810 bytes �Asynchronous Data Packet� refers to a data packet of the present invention for carrying asynchronous data. FIG. 6 depicts an embodiment of an Asynchronous Data Packet format which uses the same format as the HDLC frame format, as is known in the art, so that an HDLC frame can be transported within a Frame Cycle without any conversion. In this embodiment, an Asynchronous Frame Packet comprises leading HDLC Flag 601, Asynchronous Data Bytes 602, and trailing HDLC Flag 603, with leading HDLC Flag 601 and trailing HDLC Flag 603 each occupying one byte. In some embodiments of the present invention, the remaining transport capacity of a particular Frame Cycle can be calculated, as is known in the art, based on the known length of the Frame Cycle, the size of the Frame Synchronization Packet, and the size and number of TDM Packets to be carried during the Frame Cycle. The number of asynchronous data bytes to be carried in an Asynchronous Data Packet is then adjusted so that the Asynchronous Data Packet occupies the remaining transport capacity of the Frame Cycle. In some embodiments, an HDLC frame may be larger than the usual sizes of Asynchronous Data Packets on a particular communication channel employing the present invention. Such large HDLC frames may be split into two or more segments, with each segment being carried by a separate Asynchronous Data Packet and reassembled after all the component segments are received, as described below in this Specification.
�Subscription Bandwidth� refers, for a communication ring, to the amount of bandwidth guaranteed to be reserved on the communication ring for all of subscription traffic of that ring's nodes. Similarly, Subscription Bandwidth refers, for a particular node on a communication ring, to the amount of bandwidth guaranteed to be reserved on the communication ring for that node's subscription traffic, as is known in the art. A particular node's Subscription Bandwidth is not generally shared with other nodes on the communication ring.
�Over-Subscription Bandwidth� refers, for a communication ring, to the amount of bandwidth available after the Subscription Bandwidth for that ring is subtracted from the ring's total available bandwidth. The nodes of a communication ring generally share the ring's Over-Subscription Bandwidth as needed to transport each node's over-subscription traffic, as is known in the art.
�Maximum Over-Subscription Bandwidth� refers, for a particular node on a communication ring, to the maximum amount of Over-Subscription Bandwidth that the node may be permitted to use. In some embodiments of the present invention, the Maximum Over-Subscription Bandwidth of a particular node is set at the service provisioning time, as is known in the art, based on factors including the traffic types and number of customers, to provide access fairness for each node and minimize the effect of location-dependent advantages.
�Acceptable Over-Subscription Bandwidth� refers, for a particular node on a communication ring, to the minimum amount of Over-Subscription Bandwidth that may be made available for the node to use. Due to Congestion or other problems on the ring, as are known in the art, however, the Over-Subscription Bandwidth actually available to a node at a particular time may be less than the node's Acceptable Over-Subscription Bandwidth. In some embodiments of the present invention, the Acceptable Over-Subscription Bandwidth of a particular node is set at the service provisioning time, as is known in the art, based on factors including the traffic types and number of customers, to provide access fairness for each node and minimize the effect of location-dependent advantages.
�Access Bandwidth� refers, for a particular node on a communication ring, to the actual maximum Over-Subscription Bandwidth assigned to the node at a particular time. Access Bandwidth will never be higher than the node's Maximum Over-Subscription Bandwidth and will never be lower than the node's Acceptable Over-Subscription Bandwidth but the Over-Subscription Bandwidth actually available to the node at a particular time may be less than the Access Bandwidth due to Congestion or other ring problems, as are known in the art. �Actual Over-Subscription Bandwidth� refers, for a particular node on a communication ring, to the smaller of the node's Access Bandwidth and the over-subscription bandwidth that is actually available to the node from the ring at a particular time. Thus, actual Over-Subscription Bandwidth is never larger than the node's Access Bandwidth, but may be reduced below the node's Access Bandwidth due to conditions on the ring. The actual Over-Subscription Bandwidth is the maximum ring bandwidth that a node will use.
�Congestion� refers, for a particular node on a communication ring, to a condition where the node has more over-subscription traffic to send to the ring than can be absorbed by the actual Over-Subscription Bandwidth available to the node, and the amount of actual Over-Subscription Bandwidth available to the node is less than the node's Acceptable Over-Subscription Bandwidth. Congestion is cleared when the node has less over-subscription traffic to send to the ring than can be absorbed by the actual Over-Subscription Bandwidth available to the node, or the amount of actual Over-Subscription Bandwidth available to the node is equal to or greater than the node's Acceptable Over-Subscription Bandwidth.
FIG. 3 is a block diagram depicting an embodiment the transmission and reception of Frame Synchronization (�syn�) Packets, Asynchronous Data Packets and TDM Packets. At Transmitter 301, Frame syn packet generator 310 transmits a Frame Synchronization Packet first, then enables TDM packet generator 315, and then finally enables the asynchronous data packet generator 305. MUX 320 multiplexes the outputs of Frame syn packet generator 310, TDM packet generator 315, and asynchronous data packet generator 305 onto Communication Channel 201. At Receiver 350, FAN Out circuit 355 receives packets from Communication Channel 201 and distributes the packets for processing by Frame syn packet receiver 365, TDM packet receiver 370, and asynchronous data packet receiver 360. Frame syn packet receiver 365 first detects the Frame Synchronization Packet, then enables TDM packet receiver 370, and finally enables asynchronous data packet receiver 360.
FIG. 7 depicts a flow chart that describes, in some embodiments, the reception, decoding, and processing of received packets. Framer 701 monitors, as is known in the art, the bit stream from a communication channel and attempts to detect the unique frame code carried, in some embodiments, in Frame Synchronization Packets. When the frame code is detected, control is passed to Payload De-Scrambler and Sync Packet Processing 705 for processing of the Frame Synchronization Packets and recovery of the TDM Packets. TDM Packets are processed by TDM Packet Processor 710 until Last TDM Packet? 711 determines that all TDM Packets in the current Frame Cycle have been processed. Control is then passed to Data Packet Processor 715 for processing of any Asynchronous Data Packets. After Data Packet Processor 715 completes processing, Correct frame pattern? 720 determines if the frame code for the next Frame Cycle has been detected. If the frame code is detected, then control returns to Payload De-Scrambler and Sync Packet Processing 705, and processing continues as described above. If the frame code is not detected, then control returns to Framer 701, and Framer 701 continues to search for the frame code.
FIG. 8 depicts a flow chart that describes, for some embodiments, the operation of Data Packet Processor 715. Data Packet Processor 715 processes each byte received from the communication channel after the last TDM Packet is processed and until the expected end of the Frame Cycle is reached. Since Asynchronous Data Packets may contain partial HDLC frames, portions of Data Processor 715, particularly including Partial packet from previous frame? 801, Continue the partial data payload from previous 125 us frame 808, and Store the partial data payload for continuation in the next 125 us frame 807, deal with partial HDLC frames. Other portions of Data Processor 715 (802-806) generally deal with the processing of both full and partial HDLC frames.
Embodiments of the present invention for dynamic bandwidth sharing on a communication ring facilitates the sharing of bandwidth between multiple nodes on the ring. In various embodiments, distances between nodes can range from worldwide scales to merely a few feet. FIG. 15 depicts Communication Ring 1501 whose bandwidth is divided into two categories: one for Subscription Traffic 1515 (also referred to as committed traffic) and one for Over-Subscription Traffic 1520. The percentage of ring bandwidth assigned to each type of traffic within the ring can be dynamically and automatically adjusted. Nodes 1510 transmit traffic to Communication Ring 1501 and receive traffic from Communication Ring 1501, as is known in the art. As depicted in FIG. 15, traffic flows around the ring in a single direction. The downstream direction from a node on a ring is the direction that traffic flows on the ring. The upstream direction from a node is the direction opposite the traffic flow. As is known in the art, bi-directional rings may be created by combining two single direction rings that transport traffic in opposite directions. Embodiments of the present invention for dynamic bandwidth sharing operate on single direction rings and may be employed separately on each single direction ring of a bi-directional ring.
Stage 3 1603 (Queuing/Scheduling and RED (Random Early Detection)) Traffic is queued in preparation for being inserted onto the communication ring. The length/depth and output bandwidth of each queue are assigned based on service definitions, e.g., throughput rate, delay time, loss probability, burst sizes, and number of customers to be served, as is known in the art. During this stage, as is known in the art, the traffic is smoothed using a scheduling system, e.g. weighted Round Robin (RR) queuing, priority queuing, or hierarchical queuing. In addition, RED is implemented to drop traffic in case the depth of a particular queue exceeds a predetermined threshold.
Embodiments of the present invention provide class-based queuing and congestion management that is not based on individual data flows or particular customers. These embodiments improve the scalability of the invention. In these embodiments, traffic is categorized into two main groups: subscription (committed) and over-subscription. In some embodiments, subscription traffic includes Constant Bit Rate (CBR) and Variable Bit Rate (VBR) with normal burst size, as are known in the art. In some embodiments, over-subscription traffic includes VBR with excess burst, non-conforming VBR traffic, e.g. exceeding the mean rate, and Unspecified Bit Rate (UBR), as are known in the art. A hybrid of weighted fairness and priority queuing/scheduling is employed in some embodiments as is known in the art. In some embodiments, all subscription traffic is sent to the ring before the rest of traffic. This helps to ensure that the loss and delay of subscription traffic is minimized during the periods of congestion. In addition, reserved bandwidth may be provided on the ring for subscription traffic. In these embodiments, over-subscription traffic is not permitted to jam subscription traffic. For excess burst traffic, a separate policing device is used as is known in the art.
1. Creation and population of a traffic identification table for use in conformance verification and scheduling; 2. Real-time checking of the traffic's port address, Medium Access Control (MAC) address, IP address, or (Differentiated Services Code Point) DSCP code and determining the corresponding traffic carriage contract and parameters; and 3. Forwarding the traffic to the corresponding traffic policing system (Stage 2 1702) at the line rate. FIG. 19 depicts an example of a traffic identification table (Traffic Identification Table 1901), as is known in the art and in an embodiment of the present invention, generated during Stage 1 processing.
1. Stage 1 classification activities assign the traffic to different policing devices. In FIG. 20, for example and in this embodiment, three policing devices are used. Each policing device is set based on specific service contract requirements. For example, if there are three different PCR services, e.g. mean rates are 64 kb/s, 2 Mb/s, 4 Mb/s, then there will be three PCR buckets corresponding to these three services. In embodiments of the present invention, the number of policing devices should be equal to the number of services defined or offered by a service provider, rather than the number of physical ports or number of customers served by each node. 2. If the traffic passes PCR or VBR with normal burst size, as is known in the art, the traffic is sent to a committed buffer in Dual Port memory 1802 at the line rate. In embodiments of the present invention, there is one committed buffer for each physical port, and there is therefore no need for a temporary buffer for the committed traffic. 3. As depicted in FIG. 20, only the excess burst traffic is shown as over-subscription traffic. In some embodiments, the non-conforming traffic would be included as over-subscription traffic and put into a different class of egress queue, as is known in the art. 4. For over-subscription traffic, in the depicted embodiment, there is a temporary buffer (2005) for each physical port. This is because over-subscription traffic is stored based on classes of services. Traffic belonging to the same class but different input ports will be stored in the same queue. 5. In embodiments of the present invention, the required depth of the temporary over-subscription buffer (2005) is determined, as is known in the art, by acceptable excess burst size and the probability of accessing the corresponding Class-n over-subscription buffer (contained in Dual Port memory 1805). 6. In embodiments of the present invention, the read-out rate of the internal temporary buffer (2005) is equal to or greater than the average rate of acceptable excess burst. 7. In some embodiments, the protocol to move packets from the temporary over-subscription buffer (2005) to the Class-n over-subscription buffer (contained in Dual Port memory 1805) is based on a request from the temporary over-subscription buffer (2005) or any Class-n over-subscription buffer (contained in Dual Port memory 1805). FIG. 21 depicts, in some embodiments of the present invention, the Stage 3 operations where committed traffic is processed and multiplexed onto the ring. In these embodiments, Stage 3 performs the following operations on committed traffic:
1. The committed buffers can be implemented as one memory (Dual Port memory 1802) shared by all the physical ports or in one-to-one correspondence to each physical port with a buffer depth that supports at least one maximum acceptable burst size from each physical port, as is known in the art. 2. If, in some embodiments, all the packets coming to the committed buffers have a fixed length, i.e. Segmentation and Reassembly (SAR) is implemented in the traffic classification block, as is known in the art, then the buffer is temporary storage for waiting until it is emptied by Packet MUX 1803. 3. In embodiments of the present invention, Packet MUX 1803 ensures that there is no interleaving between packets coming from the same input port, if there is no SAR message Identification (ID), as is known in the art. 4. In embodiments of the present invention, the output rate of Packet MUX 1803 will be the sum of all committed traffic. In these embodiments, there is a corresponding bandwidth reserved on the ring and Packet MUX 1803 behaves in a similar manner to a RR multiplexor with pre-assigned bandwidth for each committed buffer, as is known in the art. In embodiments of the present invention, FIG. 22 depicts the Stage 3 operations where over-subscription traffic is processed. In these embodiments, Stage 3 performs the following operations on over-subscription traffic:
1. In some embodiments, the operation of Ring Access Controller 1806 is a hybrid of Weighted Fair (WF) and priority through the use of a return interruption mechanism, as is known in the art. Ring Access Controller 1806 uses WF to first read data out of the Class-1 over-subscription buffer, contained in Dual Port memory 1805, at a predetermined rate, then to read data out of the next Class-2 over-subscription buffer, contained in Dual Port memory 1805, at another predetermined rate, and then continues in a like manner through the rest of the over-subscription buffers. The predetermined rates provide every class with a fair amount of ring access bandwidth, i.e. weighted fairness as is known in the art. This technique is a work-conserving discipline, i.e. if the buffer is empty in a class, then the technique proceeds to the next class. In some embodiments, at periodic, predetermined time intervals, Ring Access Controller 1806 returns to the Class-1 over-subscription buffer and proceeds with data read-out as just described. In alternative embodiments, Ring Access Controller 1806 returns to the Class-1 over-subscription buffer immediately after all of the other over-subscription buffers have been read-out. 2. In some embodiments, a Maximum Over-Subscription Bandwidth and an Acceptable Over-Subscription Bandwidth are assigned to each node for use by Ring Access Controller 1806. In these embodiments, when Ring Access Controller 1806 is initialized, the node's Access Bandwidth is set equal to the node's Maximum Over-Subscription Bandwidth. The maximum ring over-subscription bandwidth available to a node and actually used by the node at a particular time is the node's actual Over-Subscription Bandwidth. When the actual Over-Subscription Bandwidth is sufficient to service all of the over-subscription buffers at their predetermined rates, Ring Access Controller 1806 operates in a RR fashion as is known in the art. When the actual Over-Subscription Bandwidth is not sufficient to service all of the over-subscription buffers at their predetermined rates, then the lower priority classes may not be read-out, and Ring Access Controller 1806 acts as a priority queue and may, in some embodiments, activate RED for certain classes of over-subscription buffers and employ return interruption as is known in the art. In these embodiments, predetermined rates assigned to the over-subscription buffers are not changed and each class may be served or not served. 3. In some embodiments, if Ring Access Controller 1806 experiences Congestion, then Ring Access Controller 1806 will send a congestion signal to all of the nodes on the ring including its own node. Ring Access Controller 1806 will send additional congestion signals at predetermined intervals until the Congestion is cleared. In some embodiments, the congestion signal will include the time and node at which Congestion occurred. When the Congestion is cleared, Ring Access Controller 1806 will send a congestion cleared signal to all of the nodes on the ring including itself. In some embodiments, the congestion cleared signal will include the time and node at which the Congestion cleared condition occurred. 4. In some embodiments, each time a congested signal is received by a node, Ring Access Controller 1806 will adjust node's Access Bandwidth in accordance with the formula:
Access Bandwidth=(Ni/Total number of nodes)�(Maximum Over-Subscription Bandwidth−Acceptable Over-Subscription Bandwidth)�(�exp n)�(Nr)+Acceptable Over-Subscription Bandwidth.
Where: Ni: the ith up-stream node from the node that originated the congested signal; the value of Ni can be predefined during service provisioning time, for example and in some embodiments, N1 is equal to 1, N2 is equal to 2, and so on in a linear fashion. n: the nth time receiving the congestion indication without receiving an intervening congestion cleared signal, e.g. the first time (� exp 1)=�, the second time (� exp 2)=�, the third time (� exp 3)=⅛, and so on. Nr: a random number, (a number for example between 1.5 and 0.5) 5. In some embodiments, each time a congestion cleared signal is received by a node, Ring Access Controller 1806 will adjust node's Access Bandwidth in accordance with the formula:
Access Bandwidth=(Maximum Over-Subscription Bandwidth−Access Bandwidth)�(n/Nr)+Access Bandwidth.
Where: Nr is an integer random number, for example and in some embodiments, an integer between 4 and 8. This random number is generated for a particular node when the congestion cleared signal is received; and n is reset to 1 each time a congestion cleared signal is received and, so long as no congestion signal is received, is incremented at predetermined periodic intervals after the congestion cleared signal is received until n equals Nr. Each time n is incremented, the Access Bandwidth is recalculated. In some embodiments, and as an example, FIG. 23 depicts a weighted fair scheduler table (WF Scheduler table 2402) used as the database for Scheduler 2401, as is known in the art, to determine which traffic from Dual Port memory 1805 should be read and sent to the ring.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4726018Aug 25, 1986Feb 16, 1988International Business Machines CorporationMethod of providing priority access to a transmission communication ringUS4817088Oct 17, 1986Mar 28, 1989British Telecommunications PlcCommunications networkUS5164938Mar 28, 1991Nov 17, 1992Sprint International Communications Corp.Bandwidth seizing in integrated services networksUS5245605Oct 4, 1991Sep 14, 1993International Business Machines CorporationIntegration of synchronous and asynchronous traffic on ringsUS5555244 *Jun 30, 1994Sep 10, 1996Integrated Network CorporationScalable multimedia networkUS5636212Jan 5, 1994Jun 3, 1997Nec CorporationBurst bandwidth reservation method in asynchronous transfer mode (ATM) networkUS5696764Jul 21, 1994Dec 9, 1997Fujitsu LimitedATM exchange for monitoring congestion and allocating and transmitting bandwidth-guaranteed and non-bandwidth-guaranteed connection callsUS5768271Apr 12, 1996Jun 16, 1998Alcatel Data Networks Inc.Virtual private networkUS5862136 *May 30, 1996Jan 19, 1999Northern Telecom LimitedTelecommunications apparatus and methodUS5864542 *Apr 29, 1996Jan 26, 1999Cisco Technology, Inc.Scalable multimedia networkUS5949789Nov 21, 1996Sep 7, 1999Xerox CorporationArbitration ring for accessing a limited bandwidth switching networkUS5970069 *Apr 21, 1997Oct 19, 1999Lsi Logic CorporationSingle chip remote access processorUS6104714Sep 17, 1997Aug 15, 2000International Business Machines CorporationMethod and apparatus for allowing communication in an isochronous traffic of asynchronous transfer mode (ATM) cells in a ring networkUS6314103Feb 20, 1998Nov 6, 2001Sprint Communications Company, L.P.System and method for allocating bandwidth for a callUS6487198 *Jun 16, 1998Nov 26, 2002Mci Communications CorporationMethod and system for unloading T1 payloads from ATM cellsUS6574224Jul 2, 1999Jun 3, 2003Nortel Networks LimitedProcessing communication trafficUS6621828 *Dec 1, 1999Sep 16, 2003Cisco Technology, Inc.Fused switch core and method for a telecommunications nodeUS6788681Feb 25, 2000Sep 7, 2004Nortel Networks LimitedVirtual private networks and methods for their operationUS7061935 *Nov 21, 2000Jun 13, 2006Transwitch CorporationMethod and apparatus for arbitrating bandwidth in a communications switchUS7522609 *Dec 23, 2004Apr 21, 2009Cisco Technology, IncPropagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical scheduleUS20030026205 *May 13, 2002Feb 6, 2003Mullendore Rodney N.Packet input thresholding for resource distribution in a network switchUS20050058136Oct 4, 2004Mar 17, 2005Lothberg L. Peter J.Method for universal transport encapsulation for internet protocol network communicationsUS20050201387May 11, 2005Sep 15, 2005Harrity & Snyder, L.L.P.Device for performing IP forwarding and ATM switching* Cited by examinerNon-Patent CitationsReference1Giroux, et al., "Queuing and Scheduling", Quality of Service in ATM networks, Chapter 5, pp. 92-95.2Part 3: Carrier sense multiple access with collision detection (CSMA/CD) access method and physical layer specifications, IEEE Std. 802.3, pp. 36-40, 1998.3Smith, "Frame Relay Principals and Applications", pp. 130-134, 1993.4Synchronous Optical Network (SONET) Transport Systems: Common Generic Criteria, Telecordia Technologies, GR-253-CORE, Issue 3, pp. 1-11, Sep. 2000.Referenced byCiting PatentFiling datePublication dateApplicantTitleUSRE44053 *Feb 25, 2010Mar 5, 2013Samsung Electronics Co., Ltd.Digital transmitter/receiver system having a robust error correction coding/decoding device and error correction coding/decoding method thereofUSRE44076 *Feb 25, 2010Mar 12, 2013Samsung Electronics Co., Ltd.Digital transmitter/receiver system having a robust error correction coding/decoding device and error correction coding/decoding method thereof* Cited by examinerClassifications U.S. Classification370/468, 370/395.41, 370/230International ClassificationH04L12/42, H04J3/06, H04J3/08, H04J3/16, H04J3/24Cooperative ClassificationH04J3/247, H04J3/1682, H04L12/42, H04L47/13European ClassificationH04L12/42, H04J3/24D, H04J3/06B6, H04J3/16C, H04J3/08ALegal EventsDateCodeEventDescriptionFeb 14, 2014ASAssignmentOwner name: TELLABS RESTON, LLC, VIRGINIAFree format text: CHANGE OF NAME;ASSIGNOR:TELLABS RESTON, INC.;REEL/FRAME:032265/0467Effective date: 20131127Dec 6, 2013ASAssignmentFree format text: SECURITY AGREEMENT;ASSIGNORS:TELLABS OPERATIONS, INC.;TELLABS RESTON, LLC (FORMERLY KNOWN AS TELLABS RESTON, INC.);WICHORUS, LLC (FORMERLY KNOWN AS WICHORUS, INC.);REEL/FRAME:031768/0155Effective date: 20131203Owner name: CERBERUS BUSINESS FINANCE, LLC, AS COLLATERAL AGENJan 15, 2013FPAYFee paymentYear of fee payment: 4Apr 16, 2007ASAssignmentOwner name: TELLABS RESTON, INC., VIRGINIAFree format text: CHANGE OF NAME;ASSIGNOR:OCULAR NETWORKS, INC.;REEL/FRAME:019162/0622Effective date: 20010213Sep 1, 2006ASAssignmentOwner name: OCULAR NETWORKS, INC., VIRGINIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:FANG, RONG C.;REEL/FRAME:018199/0707Effective date: 20011115RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services