Packet route scheduling in a packet cross connect switch system for periodic and statistical packets

• US 5,042,032 A
• Filed: 06/23/1989
• Issued: 08/20/1991
• Est. Priority Date: 06/23/1989
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Dighe, Rajiv S., May, Carl J. Jr.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Hsu, Alpus H.
• Application Number:
  US07/371,233
• Time in Patent Office: 788 Days
• Field of Search: 370/60, 370/94.1, 370/94.3, 370/16, 370/54, 370/58.1, 370/58.2, 370/58.3, 370/85.1, 370/85.6, 370/85.7, 370/95.1, 370/60.1, 340/825.03, 340/826, 340/827, 340/825.5, 340/825.51, 340/825.52, 379/271, 379/272, 379/273
• US Class Current: 370/231
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 49/102 using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

Routing of packets in a packet cross-connect switch is determined based on the particular type of packet, i.e., statistical or periodic, grade of service assigned to the packet, e.g., minimum delay, the actual queuing delay at output assigned to the particular packet destination and the status of the assigned output ports. Additionally, for periodic type packets the routing decision is also based on whether an interval is reserved for transmission of periodic packets at the assigned output ports. The routing decision is also based under certain conditions on whether or not the packet has been previously scheduled over an alternate route. The actual queuing delay at the assigned output ports is compared to predetermined delay threshold values in determining the packet route and/or whether it should be discarded. If the packet is a statistical type and it was previously scheduled over an alternate route, it will be discarded, if it is not scheduled to be routed via a primary one of the assigned output ports and the delay at a secondary, i.e., alternate, one of the assigned output ports is greater than a predetermined re-routing delay threshold value. In a specific embodiment, the delay threshold values are selected such that typically only statistical packets are scheduled for an alternate route. Periodic packets are typically scheduled for an alternate route or discarded only for catastrophic failures.

Claims

1. A packet switch comprising:

a plurality of input ports each having an input adapted for receiving packets, each packet comprising at least a transport word including packet transport information, storage means for storing received packets, a first output adapted for supplying as an output packet information from said storage means, and a second output adapted for supplying as an output packet transport information from transport words for particular packets stored in said storage means;

a plurality of output ports each having a first input adapted for receiving packet information, a second input adapted for receiving packet transport information, a first output adapted for supplying as an output packets, means for generating a representation of delay in supplying said packets as an output by said output port, and a second output for supplying as an output said representation of delay;

scheduler means responsive to said packet transport information from one of said plurality of input ports for a particular packet stored therein and to one or more of said representations of delay from said plurality of output ports for scheduling said particular packet to be supplied as an output by one or more of said plurality of output ports;

means for supplying said packet transport information from said plurality of input ports to said scheduler means;

means for interfacing said second outputs of said plurality of input ports to said first inputs of said plurality of output ports;

means for supplying said representations of delay from said plurality of output ports to said scheduler means;

means for supplying said packet transport information from said scheduler means to said second inputs of said plurality of output ports; and

means for interfacing on a one to one basis said first outputs of said plurality of output ports to output media.

2. The packet switch as defined in claim 1 wherein said scheduler means includes means responsive to said transport information for obtaining an identification of a preassigned first output port and a preassigned at least second output port for said particular packet, means for obtaining a predetermined first threshold value assigned to said particular packet, first comparison means for comparing a representation of delay from said preassigned first output port to said first threshold value and for supplying as a first output a result of said comparing and first determination means responsive to said first output for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

3. The packet switch as defined in claim 2 wherein said transport information includes at least a packet type indication, said packet type indication indicating at least whether said particular packet is a first type packet or a second type packet, wherein each of said plurality of output ports further includes means for generating a representation of intervals reserved for supplying as an output packets of said first type, and wherein said first determination means is further responsive to a representation of said reserved intervals from said preassigned first output port and to said packet type indication for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

4. The packet switch as defined in claim 3 wherein said first determination means is further responsive to a representation of said reserved intervals from said preassigned at least second output port for determining whether said particular packet should be supplied as an output by said preassigned at least second output port or discarded.

5. The packet switch as defined in claim 4 wherein said first determination means includes second comparison means for comparing said representation of delay from said preassigned at least second output port to said at least first threshold value and for supplying as a second output a result of said comparing and second determination means responsive to said second output for determining whether said particular packet should be supplied as an output by said preassigned at least second output port or discarded.

6. The packet switch as defined in claim 5 wherein said second determination means includes third determination means for determining whether said particular packet has previously been alternate routed and for generating as a third output an indication of whether said particular packet has been previously alternate routed and fourth determination means responsive to said third output for determining whether said particular packet should be supplied as an output by said preassigned at least second output port or discarded.

7. The packet switch as defined in claim 6 wherein said scheduler means further includes means for obtaining a predetermined second threshold value assigned to said particular packet, wherein said fourth determination means includes third comparison means for comparing said representation of delay from said preassigned at least second output port to said second threshold value and for generating as a fourth output the result of said comparing and means responsive to said fourth output for selecting said preassigned at least second output port for supplying said particular packet as an output or discarding said particular packet.

8. The packet switch as defined in claim 7 wherein said first threshold value is greater in value than said second threshold value.

9. The packet switch as defined in claim 3 wherein each of said plurality of output ports further includes means for generating an output port status indication indicating whether said output port is operative or not and wherein said first determination means is further responsive to a status indication from said preassigned first output port and a status indication from said preassigned at least second output port for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

10. The packet switch as defined in claim 9 wherein said type indication for said particular packet further includes a grade of service indication for said particular packet and wherein said first determination means is further responsive to said grade of service indication for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

11. The packet switch as defined in claim 10 wherein said first type packet is a periodic packet, said second type packet is a statistical type packet and said grade of service is a minimum delay grade of service.

12. The packet switch as defined in claim 3 wherein said first determination means is further responsive to a representation of said reserved intervals from said preassigned at least second output port for determining whether said particular packet should be supplied as an output by said preassigned first output port, as an output by said preassigned at least second output port or discarded.

13. The packet switch as defined in claim 12 wherein said scheduler means further includes means for obtaining a predetermined third threshold value assigned to said particular packet and a delay difference value between a first transmission route and a second transmission route assigned to a destination for said particular packet and means for utilizing said representation of delay from said preassigned first output port, said representation of delay from said preassigned at least second output port, said third threshold value and said delay difference value to determine if said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

14. The packet switch as defined in claim 13 wherein said first determination means includes second determination means for determining whether said particular packet has previously been alternate routed and for generating as a second output an indication of whether said particular packet has been previously alternate routed and third determination means responsive to said second output for determining whether said packet should be supplied as an output by said preassigned at least second output port or discarded.

15. The packet switch as defined in claim 14 wherein said scheduler means further includes means for obtaining a predetermined second threshold value assigned to said particular packet, wherein said third determination means includes second comparison means for comparing said representation of delay from said preassigned at least second output port to said second threshold value and for generating as a third output the result of said comparing and means responsive to said third output for selecting said at least second output port for supplying said particular packet as an output or discarding said particular packet.

16. The packet switch as defined in claim 15 wherein said first threshold value is greater in value than said second threshold value and said third threshold value is greater in value than said second threshold value.

17. The packet switch as defined in claim 13 wherein each of said plurality of output ports further includes means for generating an output port status indication indicating whether said output port is operative or not and wherein said first determination means is further responsive to a status indication from said preassigned first output port and a status indication from said preassigned at least second output port for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

18. The packet switch as defined in claim 17 wherein said type indication for said particular packet further includes a grade of service indication for said particular packet and wherein said first determination means is further responsive to said grade of service indication for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

19. The packet switch as defined in claim 18 wherein said first type packet is a periodic packet, said second type packet is a statistical packet and said grade of service is a minimum delay grade of service.

20. The packet switch as defined in claim 2 wherein said transport information includes at least a packet type indication, said packet type indication indicating at least whether said particular packet is a first type packet or a second type packet, and wherein said first determination means is further responsive to said packet type indication for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

21. The packet switch as defined in claim 20 wherein said type indication for said particular packet further includes a grade of service indication for said particular packet and wherein said first determination means is further responsive to said grade of service indication for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

22. The packet switch as defined in claim 21 wherein each of said plurality of output ports further includes means for generating an output port status indication indicating whether said output port is operative or not and wherein said first determination means is further responsive to a status indication from said preassigned first output port and a status indication from said preassigned at least second output port for determining whether said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

23. The packet switch as defined in claim 22 wherein said scheduler means further includes means for obtaining a predetermined third threshold value assigned to said particular packet and a delay difference value between a first transmission route and a second transmission route assigned to a destination for said particular packet and means for utilizing said representation of delay from said preassigned first output port, a representation of delay from said preassigned at least second output port, said third threshold value and said delay difference value to determine if said particular packet should be supplied as an output by said preassigned first output port, supplied as an output by said preassigned at least second output port or discarded.

24. The packet switch as defined in claim 23 wherein said first determination means includes second determination means for determining whether said particular packet has previously been alternate routed and for generating as a second output an indication of whether said particular packet has been previously alternate routed and third determination means responsive to said second output for determining whether said packet should be supplied as an output by said preassigned at least second output port or discarded.

25. The packet switch as defined in claim 24 wherein said scheduler means further includes means for obtaining a predetermined second threshold value assigned to said particular packet, wherein said third determination means includes second comparison means for comparing said first representation of delay from said preassigned at least second output port to said second threshold value and for generating as a third output the result of said comparing and means responsive to said third output for selecting said preassigned at least second output port for supplying said particular packet as an output or discarding said particular packet.

26. The packet switch as defined in claim 25 wherein said first type packet is a periodic packet, said second type packet is a statistical type packet and said grade of service is a minimum delay grade of service.

27. The packet switch as defined in claim 26 wherein said first threshold value is greater in value than said second threshold value and said third threshold value is greater than said second threshold value.

28. The packet switch as defined in claim 1 wherein said scheduler means further includes means responsive to said transport information for obtaining an output port designation for a particular packet, and wherein said scheduler means includes means responsive to said output port designation and to a representation of delay from an output port associated with said designation for determining if said particular packet is to be supplied as an output by said output port associated with said designation or an alternate one of said output ports determined in accordance with prescribed criteria.

29. The packet switch as defined in claim 28 wherein said prescribed criteria in based on indirect addressing of said particular packet in relationship to predetermined assignments made to particular ones of said output ports in the packet switch.