Source: http://www.google.com/patents/US7688824?dq=5842224
Timestamp: 2015-05-24 22:50:01
Document Index: 777788585

Matched Legal Cases: ['art 400', 'art 412', 'art 412', 'art 412', 'art 412', 'art 412', 'art 412']

Patent US7688824 - Method, system, and computer program product for suppression index reuse and ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA cable modem method, system, and computer program product are provided for payload header suppression in which a limited number of suppression indices is used to map suppression rules to data streams. Network resources are conserved by implementing precise classification algorithms to correctly identify...http://www.google.com/patents/US7688824?utm_source=gb-gplus-sharePatent US7688824 - Method, system, and computer program product for suppression index reuse and packet classification for payload header suppressionAdvanced Patent SearchPublication numberUS7688824 B2Publication typeGrantApplication numberUS 10/192,654Publication dateMar 30, 2010Filing dateJul 11, 2002Priority dateJul 11, 2001Fee statusPaidAlso published asUS8149838, US20030014764, US20080034395, WO2003007116A2, WO2003007116A3Publication number10192654, 192654, US 7688824 B2, US 7688824B2, US-B2-7688824, US7688824 B2, US7688824B2InventorsAnthony P Saladino, Rennie L Gardner, Michael R Robinson, Ajay Chandra V GummallaOriginal AssigneeBroadcom CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (9), Non-Patent Citations (2), Classifications (18), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod, system, and computer program product for suppression index reuse and packet classification for payload header suppression
US 7688824 B2Abstract
A cable modem method, system, and computer program product are provided for payload header suppression in which a limited number of suppression indices is used to map suppression rules to data streams. Network resources are conserved by implementing precise classification algorithms to correctly identify incoming packets at the cable modem as belonging to a particular data stream, which ensures that a minimum number of suppression indices are utilized. Additionally, network resources are conserved by utilizing sophisticated algorithms for reusing suppression indices when new data streams are detected by the cable modem. One such reuse algorithm involves recycling the suppression index that has been least recently used in transmitting a packet with a suppressed payload header.
This application claims the benefit of U.S. Provisional Application Ser. No. 60/304,119, filed Jul. 11, 2001, by Harrell et al., entitled “Suppression Index Re-Use and Packet Classification for Payload Header Suppression in a Cable Modem System,” incorporated herein by reference.
A cable modem method, system, and computer program product are provided for payload header suppression in which a limited number of suppression indices is used to map suppression rules to data streams. The present invention conserves network resources by implementing precise classification algorithms to correctly identify incoming packets at the cable modem as belonging to a particular data stream, which ensures that a minimum number of suppression indices are utilized. Additionally, the present invention conserves network resources by utilizing sophisticated algorithms for reusing suppression indices when new data streams are detected by the cable modem.
The transmitter portion of cable modem 108 includes an upstream burst modulator 326, a low pass filter (LPF) 328, a power amplifier 330, and diplex filter 302. Transmission begins with the construction of a data packet by MAC 314. The data packet can include data originally received from an attached user device 116 via Ethernet interface 318, which can be referred to as a “payload.” In accordance with embodiments of the present invention, MAC 314 formats the data packet in compliance with the protocols set forth in DOCSIS or, when appropriate, formats the data packet in compliance with proprietary protocol-specific payload header suppression techniques that extends beyond those set forth in DOCSIS, as will be described in further detail herein. MAC 314 outputs the data packet to upstream burst modulator 326 which converts it into analog form and modulates it onto a carrier signal in accordance with either a QPSK or 16-QAM technique.
The present invention enables cable modem 108 to classify incoming packets efficiently and precisely based on a particular flow, service, quality of service, and/or like parameter. Additionally, cable modem 108 assigns a suppression index for a proprietary protocol-specific payload header suppression technique that is based on the aforementioned parameter(s). Therefore, cable modem 108 is enabled to assure that incoming packets are suppressed using the best choice of suppression index. Although embodiments of the present invention are described below with reference to using a “data flow” to classify packets, other parameters can be implemented and are considered to be within the scope of the present invention.
The control flow of flowchart 400 begins at step 401 and passes immediately to step 403. At step 403, cable modem 108 detects an incoming data stream (e.g., from user device 116). It should be understood that the expression “data stream,” as used herein, is being used by way of example, not limitation. Data stream includes text, graphics, audio, video, voice (including voice-over-IP), or any other type of media or multimedia.
At step 415, cable modem 108 sends a first packet in the data stream in an unsuppressed form to the CMTS 104 along with the assigned suppression index and a request for the CMTS 104 to “learn” the payload header.
One suppression index reuse algorithm involves “aging” each suppression index according to the last time it was used to send a suppressed packet. Thus, suppression indices can be ranked from “most recently used” to “least recently used.” When cable modem 108 detects a new data flow that does not correspond to one of the assigned suppression indices, the “least recently used” suppression index is recycled. Recycling is achieved by assigning the “least recently used” suppression index to the new data flow and by sending a new “learn” packet, including the recycled suppression index, to CMTS 104.
The control flow of flowchart 412 begins at step 501 and passes immediately to step 503. At step 503, cable modem 108 accesses a list of suppression indices that have been “allotted” to cable modem 108 by CMTS 104. As will be described later, cable modem 108 also tracks each suppression index that has been “assigned” to a data flow. This can be implemented by keeping a second list of assigned suppression indices, or by modifying a data field in the listing of allotted suppression indices.
On the other hand, if at step 506 all allotted suppression indices have been assigned to a data flow, the control flow passes to step 518. At step 518, the “least recently used” suppression index is selected and recycled. To select the least recently used suppression index, the list that is updated at step 515 is queried to select the suppression index having the oldest time stamp. Thus, recycling is achieved by assigning the “least recently used” suppression index to a newly detected data flow.
Accordingly, flowchart 412 describes an embodiment for assigning (at step 509) or reusing (at step 518) suppression indices. Once a suppression index has been assigned or reused, the control flow ends as indicated at step 595. Referring back to FIG. 4, control passes to step 415 where a new “learn” packet is sent to CMTS 104 along with the recycled suppression index.
The control flow of flowchart 412 begins at step 601 and passes immediately to step 603. At step 603, cable modem 108 accesses a list of suppression indices that have been “allotted” to cable modem 108 by CMTS 104. As will be described later, cable modem 108 also tracks each suppression index that has been “assigned” to a data flow. This can be implemented by keeping a second list of assigned suppression indices, or by modifying a data field in the list of allotted suppression indices.
On the other hand, if at step 606 all allotted suppression indices have been assigned to a data flow, the control flow passes to step 615. At step 615, cable modem 108 returns to the beginning of the ordered list that was updated at step 612. Then, at step 609, a suppression index is assigned by selecting the suppression index at the beginning of the list, and moving it to the most recently used position at the end of the list. As each suppression index is used, it is moved to the end of the list, and the least recently used suppression index naturally floats to the beginning of the list. Therefore, each future selection is determined by pulling from the beginning of the list. As such, the “least recently used” suppression index is selected and recycled.
As described above, age is determined by considering the time, or order, in which a suppression index is “assigned” to a data flow. However, in another embodiment, age is determined from the time that each suppression index is last used to “send” a suppressed packet. As such, referring back to step 430 of FIG. 4, each time a packet is sent upstream with its assigned suppression index, a time stamp is noted (as discussed in FIG. 5) or the ordered list is updated (as discussed in FIG. 6) to reflect this operation. Accordingly, the oldest suppression index is selected and recycled as determined by the last time a packet is sent with the suppression index.
The control flow of flowchart 412 begins at step 801 and passes immediately to step 803. At step 803, cable modem 108 accesses a list of suppression indices that have been “allotted” to cable modem 108 by CMTS 104.
On the other hand, if at step 806 all allotted suppression indices have been assigned to a data flow, the control flow passes to step 812. At step 812, cable modem 108 compares the payload header of the new packet from the new data flow with the payload header of each “learn” packet that has already been associated with a suppression index.
At step 815, the suppression index associated with the payload header of the “learn” packet that is most similar to the payload header of the new packet (i.e., has the fewest number of different bits) is identified. Then at step 809, the identified suppression index is assigned to the newly detected data flow. After a suppression index has been assigned or reused, the control flow ends as indicated at step 895. This embodiment operates on the assumption that the similarity of the payload headers is a likely indication that the new data flow originates from the same source as the older data flow with which the suppression index was associated.
The control flow of flowchart 412 begins at step 901 and passes immediately to step 903. At step 903, cable modem 108 accesses a list of suppression indices that have been “allotted” to cable modem 108.
On the other hand, if at step 906 all allotted suppression indices have been assigned to a data flow, the control flow passes to step 912. At step 912, the “least often used” suppression index is selected and recycled. To select the least often used suppression index, statistical analysis is performed to determine, over time, which suppression indices are least often used. In an embodiment, the statistical analysis is performed off-line. However, in another embodiment, the present invention is configured to enable the processing to be performed in real time or near term.
In accordance with yet another embodiment, cable modem 108 performs a combination of “least recently used” processing and “least often used” processing. In an embodiment, a suppression index is selected for recycling primarily based on “least recent use,” as discussed above with reference to FIG. 5 and FIG. 6. However, where two or more suppression indices of approximately the same age are considered for recycling, the index that is recycled is the one that is least often used as determined by statistical analysis.
The control flow of flowchart 412 begins at step 1001 and passes immediately to step 1003. At step 1003, cable modem 108 accesses a list of suppression indices that have been “allotted” to cable modem 108.
On the other hand, if at step 1006 all allotted suppression indices have been assigned to a data flow, the control flow passes to step 1012. At step 1012, the “least recently used” suppression index is selected and recycled. To select the least recently used suppression index, the aging methodologies and/or techniques described with reference to FIG. 5 and FIG. 6 are implemented.
In another embodiment, a suppression index is selected for recycling based primarily on “least often use.” However, where two or more suppression indices that have experienced the same level of usage as determined by statistical analysis are considered for recycling, the suppression index that is recycled is the one that has least recently been used.
However, if all allotted suppression indices have been assigned and a new data flow is detected, the control flow passes to step 1112. At step 1112, the “least often used” suppression index is selected and recycled. To select the least often used suppression index, the statistical methodologies and/or techniques described with reference to FIG. 9 are implemented.
In this document, the terms “computer program medium” and “computer usable medium” are used to generally refer to media such as removable storage drive 1414, and a hard disk installed in hard disk drive 1412. These computer program products are means for providing software to computer system 1400. The invention, in an embodiment, is directed to such computer program products.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5745837Mar 14, 1996Apr 28, 1998Terayon CorporationApparatus and method for digital data transmission over a CATV system using an ATM transport protocol and SCDMAUS5757417Sep 23, 1997May 26, 1998International Business Machines CorporationMethod and apparatus for screening audio-visual materials presented to a subscriberUS5883901Nov 17, 1997Mar 16, 1999Hewlett-Packard CompanyCommunications system including synchronization information for timing upstream transmission of data and ability to vary slot durationUS6028860Oct 23, 1996Feb 22, 2000Com21, Inc.Prioritized virtual connection transmissions in a packet to ATM cell cable networkUS6385700 *Apr 13, 2001May 7, 2002Philips Electronics No. America Corp.Set-associative cache-management method with parallel read and serial read pipelined with serial writeUS6438123 *Jan 4, 1999Aug 20, 2002Cisco Technology, Inc.Method and apparatus for supporting header suppression and multiple microflows in a networkUS20020007417 *May 14, 2001Jan 17, 2002Diva Systems CorporationModular storage server architecture with dynamic data managementUS20020062394 *Oct 11, 2001May 23, 2002Broadcom CorporationCable modem system and method for dynamically mixing protocol specific header suppression techniquesUS20020136291Jan 17, 2002Sep 26, 2002Broadcom CorporationSystem and method for a generalized packet header suppression mechanism* Cited by examinerNon-Patent CitationsReference1Notification of Transmittal of International Preliminary Examination Report of International Application No. PCT/US02/21896, issued on Jul. 31, 2003.2Search Report for International Application No. PCT/US02/21896, issued on Mar. 13, 2003.Classifications U.S. Classification370/392, 370/477, 370/474International ClassificationH04L29/06, H04L12/28, H04L12/56Cooperative ClassificationH04L29/06, H04L29/06027, H04L69/04, H04L69/22, H04L65/607, H04L12/2801European ClassificationH04L29/06C2, H04L29/06, H04L12/28B, H04L29/06N, H04L29/06C5, H04L29/06M6ELegal EventsDateCodeEventDescriptionSep 30, 2013FPAYFee paymentYear of fee payment: 4Jul 30, 2002ASAssignmentOwner name: BROADCOM CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SALADINO, ANTHONY P.;GARDNER, RENNIE L.;ROBINSON, MICHAEL R.;AND OTHERS;REEL/FRAME:013139/0539;SIGNING DATES FROM 20020710 TO 20020724Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SALADINO, ANTHONY P.;GARDNER, RENNIE L.;ROBINSON, MICHAEL R.;AND OTHERS;SIGNING DATES FROM 20020710 TO 20020724;REEL/FRAME:013139/0539Owner name: BROADCOM CORPORATION,CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SALADINO, ANTHONY P.;GARDNER, RENNIE L.;ROBINSON, MICHAEL R. AND OTHERS;SIGNED BETWEEN 20020710 AND 20020724;US-ASSIGNMENT DATABASE UPDATED:20100330;REEL/FRAME:13139/539Owner name: BROADCOM CORPORATION,CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SALADINO, ANTHONY P.;GARDNER, RENNIE L.;ROBINSON, MICHAEL R.;AND OTHERS;SIGNING DATES FROM 20020710 TO 20020724;REEL/FRAME:013139/0539RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services