Adaptive preferential flow control for packet switching system

• US 4,616,359 A
• Filed: 12/19/1983
• Issued: 10/07/1986
• Est. Priority Date: 12/19/1983
• Status: Expired due to Term

• Current Assignee: AT&T Information Systems Inc. (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Fontenot, Michael L.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Rokoff, Kenneth I.
• Application Number:
  US06/563,256
• Time in Patent Office: 1,023 Days
• Field of Search: 370/60, 370/94, 340/825.5
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

Flow control of data packets through a packet switching network to reduce congestion is controlled by an adaptive preferential permit packet (APP) processing from an orginating data terminal through each packet switch node of the network to a destination data terminal. APP requires less buffer storage capacity at each switch node, and enables data packets to enter the network only when there is a permit packet indication that the data packets are likely to reach, and be accepted by, their destination. The permit packet is sent node to node (16-19, 25, 28) prior to a transmission of a bulk of data packets. Each node is equipped to queue buffer (12-15, 21-24) a permit packet on a preferential basis ahead of data packets. The node discards the permit packet if the number of packets awaiting transmission from that node exceeds a prescribed threshold. This is throttling process, since the originating port times out and resends a permit packet if a permit-return packet is not received within a predetermined time. Permit-return packet processing, adaptive time-out controls, and preferential treatment of permit packets are disclosed.

Claims

1. A packet flow control method for a packet switching node comprising

receiving a congestion test packet during an established packet communication session through said node, and prior to an entry of data packets into said node,

determining an absence of packet congestion in buffer storage of said node in response to a receipt of said test packet,

advancing said test packet from said node in response to the determination of an absence of congestion, and

subsequently, in response to a receipt of a congestion absent packet at said node within a prescribed timed period following said receiving of said congestion test packet, entering at least one data packet into said node for communication toward a destination.

2. The package flow control method of claim 1 wherein said determining comprises

checking, in response to a receipt of said test packet, said buffer storage of said node to ascertain whether a packet storage threshold thereof is exceeded, and

said advancing comprises sending said test packet from said node in response to said ascertaining that said storage threshold is not exceeded.

3. The packet flow control method of claim 2 further comprising

storing said test packet in said buffer storage of said node, and

prioritizing said test packet for storage in said buffer storage ahead of data packets stored therein, and behind any priorly stored test packet.

4. A packet flow control method comprising

processing a congestion test packet from a first port through a packet switching network to a second port during an established session between said ports, and prior to an entry of data packets from said first port into said network,

determining an absence of packet congestion in said network in response to a receipt of said test packet,

communicating a congestion absent packet from said second to said first port, and

entering, in response to a receipt of said congestion absent packet within a defined timed interval following a receipt of said congestion test packet for said processing, at least one data packet from said first port into said network for communication to said second port.

5. The packet flow control method of claim 4 wherein said processing comprises

storing said congestion test packet in packet buffer storage of said network, and

prioritizing said test packet for storage in said buffer storage ahead of data packets stored therein, and behind any priorly stored test packet.

6. The packet flow control method of claim 4 wherein said processing comprises

checking, in response to a receipt of said congestion test packet, packet buffer storage of said network to ascertain whether the packet storage threshold thereof is exceeded, and

advancing said test packet through said network in response to said checking ascertaining that said storage threshold is not exceeded.

7. The packet flow control method of claim 6 further comprising

storing said test packet in said buffer storage after said checking ascertains that said storage threshold is not exceeded, and

said advancing includes communicating the stored test packet through said network toward said second port.

8. The packet flow control method of claim 7 further comprising

prioritizing said test packet for storage in said buffer storage ahead of data packets stored therein, and behind any priorly stored congestion test packets.

9. A method of controlling the flow of data packets in a multinode packet switching network comprising

checking each packet buffer storage threshold of nodes of said network in response to a receipt of a permit packet,

processing said permit packet from an originating port through said checked nodes of said network to a destination port when said checking indicates that said threshold is not exceeded,

communicating a permit-return packet from said destination port through said network to said originating port in response to a receipt of said permit packet at said destination port, and

admitting a predetermined number of data packets into said network at said originating port in response to a receipt of said permit-return packet.

10. The method in accordance with claim 9 further comprising

prioritizing said permit packet in the checked buffer storage preparatory to said processing of said prioritized permit packet through said network.

11. The method in accordance with claim 10 wherein

said prioritizing comprises storing said permit packet in said checked buffer storage ahead of data packets, and behind other permit packets storable therein.

12. The method in accordance with claim 9 further comprising

prioritizing said permit-return in respect to other packets for said communicating of said permit-return packet through said network.

13. The method in accordance with claim 9 further comprising

discarding said permit packet when said checking determines that said packet buffer storage threshold is exceeded.

14. The method in accordance with claim 9 further comprising

timing for an interval prescribed for completing said processing of said permit packet through said network from said originating port, and said communicating of said permit-return packet from said destination port through said network to said originating port,

discarding the processed permit packet when said checking determines that said packet buffer storage threshold is exceeded, and

generating, upon an expiration of said timing, another permit packet for processing from said originating port through said network to said destination port.

15. The method in accordance with claim 14 further comprising

increasing said timing interval following said generating of said other permit packet, and

decreasing the increased timing interval in response to a receipt at said originating port of a permit-return packet following said processing of said other permit packet.

16. An adaptive preferential permit flow control method for a packet switching network comprising

receiving a permit packet at a switching node of said network from an originating terminal during a session between said terminal and a destination terminal via said network, and prior to an entry of data packets into said node,

recognizing said permit packet in said switching node,

checking, in response to the recognition of said permit packet, buffer storage of a queue of said switching node for determining whether a packet storage threshold thereof is exceeded,

discarding said permit packet when said checking indicates that said threshold is exceeded,

prioritizing said permit packet for storage in said queue buffer storage ahead of data packets, and behind any priorly stored permit packets therein,

sending said prioritized permit packet into said switching network toward said destination terminal,

receiving the sent permit packet at said destination terminal,

discarding the permit packet received at said destination terminal when said terminal is not ready to receive data packets,

modifying said permit packet from said destination terminal to form a permit-return packet,

sending said permit-return packet from said destination terminal to a packet switch node of said network for processing through said network to said originating terminal,

prioritizing said permit-return packet in a queue of said packet switch node behind any permit packets and data packets priorly stored therein,

sending said prioritized permit-return packet through said network toward said originating terminal, and

entering a specified number of data packets into said buffer storage of said queue in response to a receipt of said permit-return packet at said originating terminal.

17. The adaptive preferential permit flow control method of claim 16 further comprising

timing an interval prescribed for completing a communication of said permit and permit-return packet through said network between said originating and destination terminals, and

generating another permit packet from said originating terminal for sending to said buffer storage queue upon an expiration of said timing interval.

18. The adaptive preferential permit flow control method of claim 17 further comprising

multiplying said timing interval in response to the generating of said other permit packet, and

reducing the multiplied timing interval in response to a subsequent receipt of a permit-return packet from said network.

19. A packet flow control method

comprising processing a congestion test packet from a first port through a packet switching network to a second port during an established session between said ports and prior to an entry of data packets from said first port into said network,

determining an absence of packet congestion in said network in response to a receipt of said test packet,

communicating a congestion absent packet from said second to said first port,

entering, in response to a receipt of said congestion absent packet, at least one data packet from said first port into said network for communication to said second port,

discarding said congestion test packet in response to network congestion above a predetermined threshold,

timing for an interval defined for completing said processing of said congestion test packet from said first port through said network to said second port, and said communicating of said congestion absent packet from said second port through said network to said first port, and

processing another congestion test packet from said first port through said network to said second port upon an expiration of said timing interval.

20. The packet flow control method of claim 19 further comprising

increasing said timing interval upon said processing of said other congestion test packet, and

decreasing said timing interval in response to a receipt at said first port of a congestion absent packet following said processing of said other congestion test packet.

21. A packet flow control method comprising

processing a congestion test packet from a first port through a packet switching network to a second port during an established session between said ports, and prior to an entry of data packets from said first port into said network,

determining an absence of packet congestion in said network in response to a receipt of said test packet,

communicating a congestion absent packet from said second to said first port,

entering, in response to a receipt of said congestion absent packet, at least one data packet from said first port into said network for communication to said second port

timing for an interval defined for completing said processing of said congestion test packet from said first port through said network to said second port and communicating of said congestion absent packet from said second port through said network to said first port, and

processing another congestion test packet from said first port through said network to said second port upon an expiration of said timing following a receipt of said first-mentioned congestion test packet at said second port.

22. A method of controlling the flow of data packets in a multinode packet switching system comprising

processing a packet for testing congestion in buffer storage of said network from an originating port through said network to a destination port during an established session therebetween and prior to a subsequent entry of data packets into said network for said session,

determining packet congestion in any of said buffer storage of any said node of said network in response to a receipt of said congestion testing packet,

discarding said congestion testing packet in response to said determining of buffer storage congestion, and

communicating within a timed interval from said destination port through said network to said originating port a packet signifying said determining of an absence of buffer storage congestion.

23. The method in accordance with claim 22 wherein said packet congestion determining comprises

checking, in response to a receipt of said congestion testing packet, each packet buffer storage of said node of said network to ascertain whether packet storage threshold thereof is exceeded, and

said congestion testing packet processing comprises advancing said testing packet from each checked node in response to said checking ascertains that said storage threshold thereof is not exceeded.

24. The method in accordance with claim 23 further comprising

storing each congestion testing packet in packet buffer storage after said checking ascertains that said storage threshold thereof is not exceeded.

25. The method in accordance with claim 24 further comprising

prioritizing each said congestion testing packet for storage in said buffer storage ahead of data packets stored therein, and behind any priorly stored congestion testing packets.

26. The method in accordance with claim 24 further comprising

storing said signifying packet in packet buffer storage of nodes of said network for communication thereof from said destination port to said originating port, and

prioritizing said signifying packet for storage in said buffer storage ahead of data stored therein.

27. A method of controlling the flow of data packets in a multinode packet switching system comprising

processing a packet for testing congestion in said network from an originating port through said network to a destination port during an established session therebetween and prior to a subsequent entry of data packets into said network for said session,

determining packet congestion in any of said nodes of said network in response to a receipt of said congestion testing packet,

discarding said congestion testing packet in response to said determining of network congestion,

communicating from said destination port through said network to said originating port a packet signifying an absence of congestion,

timing for an interval defined for completing said processing of said congestion testing packet from said originating port through said nodes of said network and said communicating of said signifying packet from said destination port through said network to said originating port, and

processing another congestion testing packet from said originating port through said nodes of said network to said destination port upon an expiration of said timing interval.

28. The method in accordance with claim 27 further comprising

multiplying said timing interval in response to a generation of said other congestion testing packet, and

subsequently reducing the multiplied timing interval in response to a receipt of a said packet signifying an absence of network congestion.

29. In a packet network switching system including a plurality of nodes between a source node and a destination node, a packet flow control method for preempting a virtual circuit path between said source node and said destination node comprising

transmitting a pilot packet from said source node toward said destination node and prior to an entry of information packets into said source node,

assessing, in response to an arrival of said pilot packet at each said node, buffer storage capacity at said each node,

controlling, in response to said assessment of said buffer storage capacity, the forward transmission of said pilot packet, and

enabling an entry of said information packets into said source node in response to a pilot-return packet from said destination node to said source node within a predetermined timed interval.

30. The method of claim 29 further comprising moving, in response to said assessment, said pilot packet to a priority position in the node buffer.