Increased throughput across data network interface by dropping redundant packets

• US 6,700,871 B1
• Filed: 05/04/1999
• Issued: 03/02/2004
• Est. Priority Date: 05/04/1999
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Mortsolf, Timothy G., Peirce, Jr., Kenneth L., Harper, Matthew
• Primary Examiner(s): Nguyen, Steven H. D
• Application Number:
  US09/305,133
• Time in Patent Office: 1,764 Days
• Field of Search: 370/229-238, 370/428-429, 370/400-408, 370/477, 709/203, 709/219, 709/224, 709/223, 709/229, 709/225, 714/746-750
• US Class Current: 370/235
• CPC Class Codes: H04L 1/1877 for semi-reliable protocols, e.g. for less sensitive applications like streaming video buffer level management for video bitstream control arrangements H04N21/44004
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/2872 Termination of subscriber connections
• CPC Class Codes: H04L 2001/0092 Error control systems characterised by the topology of the transmission link
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

In a typical remote access application, such as access from the home to a packet-switched high speed network such as the Internet, the low-speed dial up connection to a network access is the main bottleneck in terms of the bandwidth and efficiency of transfer of data across the network access server. The present invention increases throughput through the network access server by identifying and dropping redundant, e.g., retransmitted, packets en route from the LAN or WAN to the remote terminal, thereby preserving precious bandwidth.

Claims

1. A method for increasing the throughput of data through a device providing an interface between a first network and a second network, comprising the steps of:

receiving a packet from a source of data at said interface, said packet transported along said first network;

determining if said packet either contains data previously forwarded across said interface and onto said second network for transmission to a recipient of said packet, or else data already received in said device but not yet forwarded;

dropping said packet if said packet contains data either previously forwarded across said interface or already received but not yet forwarded;

placing packets en route from said source of data on said first network to said recipient in a first queue in said device, said packets in said first queue having a packet sequence number;

placing packets en route from said recipient to said source of data in a second queue in said device, said packets en route from said recipient to said source of data containing an acknowledge sequence number;

determining a highest acknowledge sequence number for all of said packets in said second queue;

comparing said packet sequence numbers of said packets in said first queue with said highest acknowledge sequence number; and

determining whether to drop a packet from said first queue, the step of dropping being performed if a packet in said first queue has a packet sequence number lower than said highest acknowledge sequence number.

2. The method of claim 1, wherein said first network comprises the Internet and wherein said second network comprises a public switched telephone network.

3. The method of any one of claims 1 and 2, wherein said packet comprises a header portion and a data portion, and wherein said step of dropping said packet comprises the step of dropping said data portion of said packet but not dropping said header portion.

4. The method of claim 1, wherein said method is performed in a network access server comprising a telephone line interface module providing an interface to a public switched telephone network, and a gateway module providing an interface to said first network, wherein said first network comprises a packet-switched network, and wherein said network access server drops packets that are retransmitted from said source of data to said recipient so as to reduce the amount of data transmitted to said recipient over said public switched telephone network.

5. The method of claim 1, wherein said steps are performed substantially continuously during the duration of a communication session between said source of data and said recipient.

6. The method of claim 1, wherein the method further comprises the steps of:

checking the packet sequence number of said packets in said first queue; and

deleting packets in said first queue which have the same packet sequence number.

7. The method of claim 1, wherein said interface further comprises a network layer protocol software module processing a network layer protocol for said packets, and a link layer protocol software module processing a link layer protocol for said packets, and

wherein said network layer protocol software performs said steps of determining and dropping prior to processing of said link layer protocol by said link layer protocol software module.

8. The method of claim 7, wherein said network layer protocol software module comprises an IP stack and wherein said link layer protocol software module comprises a PPP stack.

9. The method as claimed in any one of claim 1, 5, or 6, wherein said method is performed in a network access server and wherein said first network comprises a packet-switched network and said second network comprises a public switched telephone network.

10. The method as claimed in any one of claims 1, 5 and 6, wherein said method is performed in a network access server and wherein said first network comprises a packet-switched network and said second network comprises a public switched telephone network, and wherein said network access server performs said method simultaneously for a plurality of different communications sessions between a plurality of different recipients and a plurality of different sources of data on said packet switched network, thereby increasing the throughput of said communications sessions.

50. The method claimed as in any one of claims 2, 4, 1, 13, 17, and 25-35 and 37-44, wherein the method is implemented in an application specific integrated circuit installed in a communications device providing an interface between a first network and a second network.

11. A method for increasing the throughput of data through a device providing an interface between a first network and a second network, comprising the steps of:

receiving a packet from a source of data at said interface, said packet transported along said first network;

determining if said packet either contains data previously forwarded across said interface and onto said second network for transmission to a recipient of said packet, or else data already received in said device but not yet forwarded; and

dropping said packet if said packet contains data either previously forwarded across said interface or already received but not yet forwarded, wherein said method is performed in a network access server comprising a telephone line interface module providing an interface to a public switched telephone network, and a gateway module providing an interface to said first network, wherein said first network comprises a packet switched network, and wherein said network access server drops packets that are retransmitted from said source of data to said recipient so as to reduce the amount of data transmitted to said recipient over said public switched telephone network, and wherein said method further comprises the steps of;

(a) placing packets en route from said source of data on said packet switched network to said recipient in a first queue, said packets in said first queue having a packet sequence number;

(b) placing packets en route from said recipient to said source of data in a second queue, said packets en route from said recipient to said source of data containing an acknowledge sequence number indicating the receipt of a packet from said source of data;

(c) determining a highest acknowledge sequence number for all of said packets in said second queue;

(d) comparing said packet sequence numbers of said packets in said first queue with said highest acknowledge sequence number; and

(e) determining whether to drop a packet from said first queue, the step of dropping performed if a packet from said first queue has a packet sequence number lower than or equal to said highest acknowledge sequence number.

12. The method of claim 11, wherein the method further comprises the steps of:

(f) checking the packet sequence number of said packets in said first queue; and

(g) deleting packets in said first queue which have the same packet sequence number.

13. A method for increasing the throughput of data through a device providing an interface between a first network and a second network, comprising the steps of:

receiving a first packet at said interface, said packet generated by a source of data connected to said first network and directed to a remote terminal connected to said second network, said first packet having a packet sequence number;

receiving a second packet at said interface, said packet generated by said remote terminal and destined for said source of data, said second packet comprising an acknowledge sequence number indicating the receipt of a packet from said source of data;

comparing said acknowledge sequence number with said packet sequence number; and

dropping said first packet if said comparison of said acknowledge sequence number with said packet sequence number indicates that data in said first packet has been received by said remote terminal, wherein said second packet is placed in a queue along with a plurality of other packets from said remote terminal, and wherein said step of comparing comprises the steps of determining a highest acknowledge sequence number for all of said packets in said queue and dropping said first packet if said packet sequence number indicates that data in said first packet has been received by said remote terminal.

14. The method of claim 13, wherein said first network comprises a packet switched network and said second network comprises a public switched telephone network.

15. The method of claim 13, wherein said method is performed in a network access server providing said interface between said first network and said second network.

16. The method of claim 13, wherein said first and second networks are characterized by having different transmission rates.

17. The method of claim 16, wherein said first network comprises a packet switched network and said second network comprises a public switched telephone network.

18. The method as claimed in any one of claims 13-17, wherein said packet contains a header portion and a data portion, and wherein said step of dropping comprises the step of dropping the data portion of said packet, with said header portion being transmitted to said remote terminal.

19. The method of claim 13, wherein said method is performed in a network access server comprising a telephone line interface module providing an interface to a public switched telephone network, and a gateway module providing an interface to said first network, wherein said first network comprises a packet-switched network, and wherein said network access server drops packets that are retransmitted from said source of data to said recipient so as to reduce the amount of data transmitted to said remote terminal over said telephone line interface module and said public switched telephone network.

20. The method of claim 13, further comprising the steps of:

placing packets en route from said first network to said second network in a queue;

checking the packet sequence number of said packets in said queue; and

dropping packets from said queue which have the same packet sequence number.

21. The method of claim 13, wherein said device further comprises a network layer protocol software module processing a network layer protocol for said packets, and a link layer protocol software module processing a link layer protocol for said packets, and

wherein said network layer protocol software performs said steps of comparing and dropping prior to processing of said link layer protocol by said link layer protocol software module.

22. The method of claim 21, wherein said network layer protocol software module comprises an IP stack and wherein said link layer protocol software module comprises a PPP stack.

23. The method of claim 13, wherein said steps of receiving a first packet, receiving a second packet, comparing and dropping are performed substantially continuously during the duration of a communication session between said source of data and said remote terminal.

24. The method of claim 13, wherein said method is performed in a network access server and wherein said first network comprises a packet-switched network and said second network comprises a public switched telephone network, and wherein said network access server performs said method simultaneously for a plurality of different communications sessions between a plurality of different remote terminals and a plurality of different sources of data on said packet switched network, thereby increasing the throughput of said communications sessions.

25. A method for increasing the throughput of data through a device providing an interface between a first network and a second network, comprising the steps of:

(1) receiving a plurality of data packets at said interface and placing said packets in a first queue, said plurality of packets including a first packet, said packets of data generated by a source of data connected to said first network and directed to a remote terminal connected to said second network, each of said packets of data having a packet sequence number;

(2) setting an expected transmission sequence number for said first queue equal to the lowest packet sequence number of all of said packets in said first queue; and

(3) processing said first packet to determine whether data in said first packet has already been transmitted to said remote terminal, said step of processing comprising the steps of;

(a) comparing the packet sequence number of said first packet with said expected transmission sequence number, and

(b) dropping data from said first packet if said first packet has a packet sequence number equal to said expected transmission sequence number and if another packet is present in said first queue with a packet sequence number equal to said expected transmission sequence number.

26. The method of claim 25, wherein said device comprises a network access server and wherein said first network comprises a packet-switched network and said second network comprises a public switched telephone network.

27. The method of claim 25, wherein said first network comprises the Internet and wherein said second network comprises a public switched telephone network.

28. The method of claim 25, wherein said method is performed in a network access server comprising a telephone line interface module providing an interface to a public switched telephone network, and a gateway module providing an interface to said first network, wherein said first network comprises a packet-switched network, and wherein said network access server drops retransmitted data from said source of data so as to reduce the amount of data transmitted to said remote terminal over said public switched telephone network.

29. The method of claim 25, wherein the method further comprises the steps of:

(4) placing packets en route from said remote terminal to said source of data in a second queue in said device, said packets en route from said remote terminal to said source of data containing an acknowledge sequence number indicating the receipt of a packet from said source of data;

(5) determining a highest acknowledge sequence number for all of said packets in said second queue;

(6) comparing said packet sequence numbers of said packets in said first queue with said highest acknowledge sequence number; and

(7) determining whether to drop a packet from said first queue, the step of dropping performed if a packet in said first queue has a packet sequence number lower than said highest acknowledge sequence number.

30. The method of claim 25, wherein said steps are performed substantially continuously during the duration of a communication session between said source of data and said remote terminal.

31. The method of claim 25, wherein said interface further comprises a network layer protocol software module processing a network layer protocol for said packets, and a link layer protocol software module processing a link layer protocol for said packets, and

wherein said network layer protocol software performs said steps of dropping prior to processing of said link layer protocol by said link layer protocol software module.

32. The method of claim 31, wherein said network layer protocol software module comprises an IP stack and wherein said link layer protocol software module comprises a PPP stack.

33. The method of claim 25, wherein said method is performed in a network access server comprising a telephone line interface module providing an interface to a public switched telephone network, and a gateway module providing an interface to said first network, wherein said first network comprises a packet-switched network, and wherein said network access server drops packets that are retransmitted from said source of data to said remote terminal so as to reduce the amount of data transmitted to said remote terminal over said public switched telephone network, and wherein the method further comprises the steps of:

placing packets en route from said remote terminal to said source of data in a second queue, said packets en route from said remote terminal to said source of data containing an acknowledge sequence number indicating the receipt of a packet from said source of data;

determining a highest acknowledge sequence number for all of said packets in said second queue;

comparing said packet sequence numbers of said packets in said first queue with said highest acknowledge sequence number; and

determining whether to drop a packet from said first queue, the step of dropping performed if a packet from said first queue has a packet sequence number lower than said highest acknowledge sequence number.

34. The method as claimed in claim 29, wherein said method is performed in a network access server and wherein said first network comprises a packet-switched network and said second network comprises a public switched telephone network, and wherein said network access server performs said method simultaneously for a plurality of different communications sessions between a plurality of different remote terminals and a plurality of different sources of data on said packet switched network, thereby increasing the throughput of said communications sessions.

35. The method of claim 25, wherein said steps of receiving, setting and processing said first packet are performed substantially continuously during the duration of a communication session between said source of data and said remote terminal.

36. A method for increasing the throughput of data through a device providing an interface between a first network and a second network, comprising the steps of:

receiving a plurality of data packets at said interface and placing said packets in a queue, said packets generated by a source of data connected to said first network and directed to a remote terminal connected to said second network, each of said packets having a packet sequence number;

processing said queue to drop retransmitted packets, said step of processing comprising the steps of;

(a) comparing said packet sequence numbers of said packets in said queue; and

(b) dropping a packet in said queue if said packet has a packet sequence number that is the same as a packet sequence number of another packet in said queue;

placing packets en route from said remote terminal to said source of data in a second queue in said device, said packets en route from said remote terminal to said source of data containing an acknowledge sequence number indicating the receipt of a packet from said source of data;

determining a highest acknowledge sequence number for all of said packets in said second queue;

comparing said packet sequence numbers of said packets in said queue with said highest acknowledge sequence number; and

determining whether to drop a packet from said queue, the step of dropping performed if a packet in said queue has a packet sequence number lower than said highest acknowledge sequence number.

37. The method of claim 36, wherein said steps of receiving and processing are performed for all of said packets in said queue.

38. The method of claim 36, wherein the method is performed continuously during the duration of a communication session between said source of data and said remote terminal.

39. The method of claim 36, wherein said method is performed in a network access server providing simultaneous access to a plurality of sources of data on a packet-switched network for a plurality of remote terminals in a plurality of simultaneously occurring communication sessions, and wherein the method is performed substantially continuously for each of said communication sessions.

40. The method of claim 39, wherein the method further comprises the steps of placing all of the packets from said sources of data in a system queue in said network access server, identifying all of the queued packets in said system queue which correspond to the same communication session based on addressing information associated with said packets, and performing said step of processing said packets for each of said communications sessions.

41. The method of claim 38, wherein the method is performed in a network access server providing simultaneous access to a plurality of sources of data on a packet-switched network for a plurality of remote terminals in a plurality of simultaneously occurring communication sessions, and wherein said method is performed substantially continuously for each of said communication sessions.

42. The method as claimed in any one of claims 37-41, wherein said packet comprises a header portion and a data portion, and wherein said step of dropping said packet comprises the step of dropping the data portion of said packet.

43. A machine-readable storage media containing a set of 1instructions for processing packets in transit through a network access server from a source of data on a first network to a remote terminal on a second network, said packets in transit placed in a first queue and each having a packet sequence number, said set of instructions comprising:

a routine for determining a highest acknowledge sequence number for packets in a second queue in said network access server, said packets en route from said remote terminal to said source of data;

a routine for comparing said highest acknowledge sequence number with the packet sequence numbers of said packets in said first queue; and

a drop routine for dropping packets in said first queue, said drop routine dropping a packet in said first queue if said packet has a packet sequence number lower than said highest acknowledge sequence number.

44. A machine-readable storage media comprising a set of instructions for a communications device providing an interface between a first network and a second network, the set of instructions, when executed, provide for the communications device to perform the following functions:

(1) receiving a plurality of data packets at said interface and placing said packets in a first queue, said plurality of packets including a first packet, said packets of data generated by a source of data connected to said first network and directed to a remote terminal connected to said second network, each of said packets of data having a packet sequence number;

(2) setting an expected transmission sequence number for said first queue equal to the lowest packet sequence number of all of said packets in said first queue; and

(3) processing said first packet to determine whether data in said first packet has already been transmitted to said remote terminal, said step of processing comprising the steps of;

(a) comparing the packet sequence number of said first packet with said expected transmission sequence number; and

(b) dropping data from said first packet if said first packet has a packet sequence number equal to said expected transmission sequence number and if another packet is present in said queue with a packet sequence number equal to said expected transmission sequence number;

(4) placing packets en route from said remote terminal to said source of data in a second queue in said device, said packets en route from said remote terminal to said source of data containing an acknowledge sequence number indicating the receipt of a packet from said source of data;

(5) determining a highest acknowledge sequence number for all of said packets in said second queue;

(6) comparing said packet sequence numbers of said packets in said first queue with said highest acknowledge sequence number; and

(7) determining whether to drop a packet from said first queue, the step of dropping performed if a packet in said first queue has a packet sequence number lower than said highest acknowledge sequence number.

45. The machine-readable storage media of claim 44, wherein said communications device comprises a network access server.

46. An application specific integrated circuit for installation in a communications device providing an interface between a first network and a second network, said application specific integrated circuit comprising:

circuitry receiving a plurality of data packets at said interface and placing said packets in a first queue, said plurality of packets including a first packet, said packets of data generated by a source of data connected to said first network and directed to a remote terminal connected to said second network, each of said packets of data having a packet sequence number;

circuitry setting an expected transmission sequence number for said first queue equal to the lowest packet sequence number of all of said packets in said first queue;

circuitry processing said first packet to determine whether data in said first packet has already been transmitted to said remote terminal, said step of processing comprising the steps of;

comparing the packet sequence number of said first packet with said expected transmission sequence number; and

dropping data from said first packet if said first packet has a packet sequence number equal to said expected transmission sequence number and if another packet is present in said queue with a packet sequence number equal to said expected transmission sequence number;

circuitry placing packets en route from said remote terminal to said source of data in a second queue in said device, said packets en route from said remote terminal to said source of data containing an acknowledge sequence number indicating the receipt of a packet from said source of data;

circuitry determining a highest acknowledge sequence number for all of said packets in said second queue;

circuitry comparing said packet sequence numbers of said packets in said first queue with said highest acknowledge sequence number; and

circuitry determining whether to drop a packet from said first queue, the step of dropping performed if a packet in said first queue has a packet sequence number lower than said highest acknowledge sequence number.

47. In a communications device providing an interface between a relatively high speed packet switched network and a relatively low speed communications medium, the improvement comprising:

a first system queue for holding packets en route through network access server from a host source of data on said packet switched network to a remote terminal;

a second system queue for holding packets en route through said network access server from said remote terminal to said network access server; and

a packet processing means for processing packets in said first system queue and dropping redundant packets which may be present in said first system queue, wherein said packet processing means comprises;

a routine for determining a highest acknowledge sequence number for packets in a second queue in said network access server,

a routine for comparing said highest acknowledge sequence number with the packet sequence numbers of said packets in said first queue; and

a drop routine for dropping packets in said first queue, said drop routine dropping a packet in said first queue if said packet has a packet sequence number the same as or lower than said highest acknowledge sequence number.

48. The improvement of claim 47, wherein said packet processing means comprises:

a compare routine for comparing packet sequence number for packets in said first queue; and

a drop routine for dropping packets in said first queue if more than one of said packets in said queue have the same packet sequence number.

49. The improvement of claim 57, wherein said packets comprise a header portion and a data portion and wherein said drop routine drops the data portion of said packets but does not drop said header portion.