Arrangement for routing data packets through a circuit switch

• US 4,556,972 A
• Filed: 12/27/1983
• Issued: 12/03/1985
• Est. Priority Date: 12/27/1983
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Martin, Ronald B., Lee, Kwok P., Chan, Dominic K.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Kuntz, Curtis
• Application Number:
  US06/565,230
• Time in Patent Office: 707 Days
• Field of Search: 370/60, 370/94, 370/92, 370/95, 370/89
• US Class Current: 370/354
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion

Abstract

Disclosed is arrangement (101, 102, 110) for routing data packets designated for a particular destination (103) from a packet switch (114) through a circuit switch (120). The packet switch includes a plurality of output links (152, 153) connected to the circuit switch and a memory (209) for storing the identity of the output links designated for use to a particular destination. The circuit switch has a plurality of channels (190) to the particular destination and a switching network (121) for interconnecting an equal number of the channels and the designated output links. Included in the arrangement is a circuit allocator (110) that monitors the use of each of the designated links. When the overall use of the designated output links is greater than an upper threshold, the allocator causes the packet switch to increase the number of links designated for use to the particular destination and subsequently causes the circuit switch to correspondingly increase the number of channels interconnecting with the output links designated for use to the particular destination. The number of designated output links is similarly decreased when the designated overall use of the output links falls below a lower threshold. A predetermined algorithm is used to determine the upper and lower thresholds for each number of output links designated for use to the particular destination.

Claims

1. An arrangement for routing data packets through a circuit switch;

comprising;

a packet switch having a plurality of output links connected to said circuit switch and memory means for storing the identity of said output links designated for use to a particular destination;

said circuit switch having a plurality of channels to said particular destination and means for interconnecting said designated output links with a number of said channels equal to the number of said output links designated for use to said particular destination; and

allocator means responsive to data packets on said designated output links for causing said packet switch to change the number of said output links designated for use to said particular destination when the overall use of said designated output links reaches a threshold.

2. The arrangement in accordance with claim 1 in which said allocator means comprises control means responsive to the change in the identity of said output links designated for use to said particular destination for causing said circuit switch to change the number of said channels interconnecting with said output links designated for use to said particular destination.

3. The arrangement in accordance with claim 1 in which said allocator means comprises:

monitor means responsive to the busy/idle condition of each of said designated output links for determining the overall use of said designated output links and

control means for causing said packet switch to change the number of said output links designated for use to said particular destination when the overall use of said designated output links reaches said threshold.

4. The arrangement in accordance with claim 3 in which said monitor means comprises link utilization means responsive to the busy/idle condition of each of said designated output links for ascertaining the individual use of each of said designated output links and

destination utilization means responsive to the individual use of each of said designated output links for ascertaining the overall use of said designated output link.

5. The arrangement in accordance with claim 4 in which said link utilization means comprises:

counter means responsive to the busy/idle condition of each of said designated output links for changing an individual count contained therein for each of said designated output links and representative of the individual use of each of said designated output links and

latch means for storing the individual count representative of the individual use of each of said designated output links.

6. The arrangement in accordance with claim 4 in which said destination utilization means comprises:

arithmetic means responsive to the individual use of each of said designated output links for determining the overall use of said designated output links and

memory means for storing the overall use of said designated output links.

7. The arrangement in accordance with claim 3 in which said control means comprises

logic means responsive to the number of said output links designated for use to said particular destination for comparing said threshold and the overall use of said designated output links and

controller means for causing said packet switch to change the number of said output links designated for use to said particular destination when the overall use of said designated output links reaches said threshold.

8. The arrangement in accordance with claim 7 in which said logic means comprises:

memory means for storing said threshold level for the number of said output links designated for use to said particular destination and

comparator means for comparing said threshold and the overall use of said designated output links.

9. An arrangement for routing data packets through a circuit switch;

comprising;

a packet switch having a plurality of output links coupled to said circuit switch and memory means for storing the identity of said output links designated for use to a particular destination;

said circuit switch having a plurality of channels to said particular destination and means for interconnecting said designated output links with a number of said channels equal to the number of said output links designated for use to said particular destination; and

allocator means for causing said packet switch to increase the number of said output links designated for use to said particular destination when the overall use of said designated output links is greater than a first threshold and to decrease the number of said output links designated for use to said particular destination when the overall use of said designated output links is less than a second threshold.

10. The arrangement in accordance with claim 9 in which allocator means comprises control means responsive to the increase in the number of said output links designated for use to said particular destination for causing said circuit switch to correspondingly increase the number of said channels interconnecting with said output links designated for use to said particular destination and wherein said control means is also responsive to the decrease in the number of said output links designated for use to said particular destination for causing said circuit switch to correspondingly decrease the number of said channels interconnecting with said output links designated for use to said particular destination.

11. The arrangement in accordance with claim 9 in which said allocator means comprises:

monitor means responsive to the busy/idle condition of each of said designated output links for determining the overall use of said designated output links and

control means for causing said packet switch to increase the number of said output links designated for use to said particular destination when the overall use of said designated output links is greater than said first threshold and to decrease the number of said output links designated for use to said particular destination when the overall use of said designated output links is less than said second threshold.

12. The arrangement in accordance with claim 11 in which said monitor means comprises link utilization means responsive to the busy/idle condition of each of said designated output links for ascertaining the individual use of each of said designated output links and

destination utilization means responsive to the individual use of each of said designated output links for ascertaining the overall use of said designated output links.

13. The arrangement in accordance with claim 12 in which said link utilization means comprises:

counter means responsive to the busy/idle condition of each of said designated output links for changing an individual count contained therein for each of said designated output links and representative of the individual use of each of said designated output links and

latch means for storing the individual count representative of the individual use of each of said designated output links.

14. The arrangement in accordance with claim 11 in which said destination utilization means comprises:

arithmetic means responsive to the individual use of each of said designated output links for determining the overall use of said designated output links and

memory means for storing the overall use of said designated output links.

15. The arrangement in accordance with claim 11 in which said control means comprises:

logic means responsive to the number of output links designated for use to said particular destination for comparing the overall use of said designated output links with said first and second thresholds and

controller means for causing said packet switch to increase the number of said output links designated for use to said particular destination when the overall use of said designated output links is greater than said first threshold and to decrease the number of said output links designated for use to said particular destination when the overall use of said designated output links is less than said second threshold.

16. The arrangement in accordance with claim 15 in which said logic means comprises:

first comparator means for comparing the overall use of said designated output links with said first threshold and

second comparator means for comparing the overall use of said designated output links with said second threshold.

17. The arrangement in accordance with claim 15 in which said logic means comprises memory means for storing said first and second thresholds for the number of said output links designated for use to said particular destination;

memory means for storing third and fourth thresholds for the increased number of said output links designated for use to said particular destination; and

memory means for storing fifth and sixth thresholds for the decreased number of said output links designated for use to said particular destination.

18. The arrangement in accordance with claim 17 wherein said first, third, and fifth thresholds ρ

₊.sup.(n) =ρ

.sup.(n) +3σ

for the number n of said output links designated for use to said particular destination;

such that the maximum theoretical input mean

ρ

.sup.(n) =min;

where the maximum steady state utilization

ρ

₁.sup.(n) =1-1/1000D(nG);

the maximum transient utilization

ρ

₂.sup.(n) ≦

1-1/1000D(nG), when t₁ '"'"'<

-T₀ ;

the maximum transient utilization

ρ

₂.sup.(n) -1+(λ

'"'"'/nG) (t'"'"'₁ /To), where T₀ =(2nG)^1/3 /(λ

'"'"')^2/3, when t'"'"'₁ ≧

-T₀ ; and

where

σ

=a standard deviation,

D=the mean delay of data packets to said particular destination,

G=the minimum bandwidth granularity of said designated output links,

λ

'"'"'=the maximum rate of increase in the input mean of data packets designated for said particular destination; and

t'"'"'₁ =time.

19. The arrangement in accordance with claim 17 wherein said second, fourth, and sixth thresholds ρ

_-.sup.(n) =0.7λ

_min.sup.(n) for the number n of said output links designated for use to said particular destination, such that

λ

_min.sup.(n)=λ

_max.sup.(n-1), where λ

_max.sup.(0) =0;

λ

_max.sup.(n)=λ

_min.sup.(n+1) ; and

λ

_max.sup.(n) =nG-1/1000D, where

D=the mean delay of data packets to said particular destination; and

G=the minimum bandwidth granularity of each of said designated output links.

20. For use with a packet switch and a circuit switch, said packet switch having a plurality of output links connected to said circuit switch and memory means for storing the identity of said output links designated for use to a particular destination, said circuit switch having a plurality of channels to said particular destination and means for interconnecting said designated output links with a number of said channels equal to the number of said output links designated for use to said particular destination, an allocation arrangement for causing the packet switch to change the number of output links designated for use to a particular destination dependent on the overall use of the designated output links comprising:

monitor means responsive to the busy/idle condition of each of said designated output links for determining the overall use of said designated output links and

control means for causing said packet switch to change the number of said output links designated for use to said particular destination when the overall use of said designated output links reaches a threshold.

21. For use with a packet switch and a circuit switch, said packet switch having a plurality of output links connected to said circuit switch and memory means for storing the identity of said output links designated for use to a particular destination, said circuit switch having a plurality of channels to said particular destination and means for interconnecting said output links designated for use to said particular destination with a number of said channels equal to the number of said output links designated for use to said particular destination, an allocation arrangement for causing the packet switch to change the number of output links designated for use to a particular destination dependent on the overall use of the designated output links comprising:

monitor means responsive to the busy/idle condition of each of said designated output links for determining the overall use of said designated output links and

control means for causing said packet switch to increase the number of said output links designated for use to said particular destination when the overall use of said designated output links is greater than a first threshold and to decrease the number of said output links designated for use to said particular destination when the overall use of said designated output links is less than a second threshold.