Routing and rate control in a universal transfer mode network

A transfer rate regulation mechanism for a data packet switch, comprising:

• a) a first plurality of buffers for storing an identity of data packets sorted into traffic streams of data packets associated with one or more communications sessions, the communications sessions being logically related;
• b) a transfer rate allocation of normalized data units for each traffic stream which is stored in a rate allocation memory, the rate allocation being an accumulation of rate allocations assigned to communications sessions in the respective traffic streams on admission of the communications session to a network that includes the data packet switch;
• f) a transfer credit stored in a transfer credit memory, the transfer credit being an accumulation of the normalized data units plus any normalized data units carried forward from a last transfer of packets from the respective traffic streams;
• g) a rate regulator for transferring the data packets from the first plurality of buffers to a second plurality of buffers as the data packets are eligible using parallel arithemetic calculations to compute an eligibility for transfer based on the transfer credits, whereby a data packet is eligible for transfer to a one of the second plurality of buffers when a transfer credit accumulated is equal to or greater than a number of data units in the data packet;
• and
• h) an egress selector for selecting packets from the second plurality of buffers in accordance with a respective transfer credit using parallel arithmetic calculations to determine a number of packets to be eligible for transfer based on accumulated transfer credits.

A routing and grade-of-service control mechanism for a switch module of a universal transfer mode (UTM) network, comprising:

• a memory for storing a sorted list of routes from the switch module to each other switch module in the UTM network,
• a routing request queue at each ingress port of the switch module,
• at least one routing progress queue at each egress port of the switch module,
• a routing request processor at each ingress port of the switch module,
• a routing progress processor at each egress port of the switch module, and
• a switch module routing processor adapted to communicate with each of the routing request processors and the routing progress processors.

A method of routing a path or an independent connection between an originating switch module and a destination switch module in a highly-connected network, comprising the steps of:

• a) enabling a network controller to store an identification and a cost of each available route from each switch module in the network to each other switch module in the network, to identify each two-hop route between each pair of switch modules in the network and to distribute to each switch module a list of the two-hop routes from the switch module to each other switch module in the network;
• b) enabling each switch module to store and update information respecting an uncommitted capacity of each link from the switch module to each of its neighboring switch modules;
• and
• c) enabling each switch module to find a route for a connection admission request received from a local source by sending at least one routing request to at least one other switch module to determine the uncommitted capacity of a link involved in the route from the other module to a destination switch module in the network;
• and
• d) selecting a route for the connection admission request based on a parameter determined by a function using a least of the uncommitted capacities of two links involved in a route and a cost factor associated with the each of the two routes.

A method of fast route setup for a connection admission request between an originating switch module and a destination switch module in a packet network, comprising the steps of:

• a) for each respective connection request, computing at a central control element of the originating switch module a cost-weighted uncommitted capacity of a set of designated routes selected from a table which stores a normalized cost of each route and an uncommitted capacity of each route to the destination switch module, and selecting a route from the designated routes according to a predefined rule;
• b) reducing the uncommitted capacity of an adjacent link in the route according to a bit-rate specified in the connection admission request;
• c) communicating with an intermediate switch module of the selected route, if the route includes an intermediate switch module, to reduce the uncommitted capacity of a link to the destination switch module;
• and
• d) communicating with the destination switch module of the selected route to reduce the uncommitted capacity of a link to a sink for the connection request, whereby each the connection requests are routed in a sequential order.

A method of transfer rate allocation for traffic streams in a shared path through a switched data network, the shared path being used to transfer a plurality of traffic streams, and identity of data packets of each traffic stream being stored in a traffic stream buffer, each traffic stream having an assigned quality-of-service index, but none of the traffic streams having a predefined transfer rate allocation, comprising, at a predefined interval, the steps of:

• a) monitoring an occupancy of a traffic stream buffer which represents a count of data units in each traffic stream,
• b) storing a current occupancy of each traffic stream buffer in a first memory;
• c) storing a previous occupancy of each traffic stream buffer in a second memory;
• d) comparing the current occupancy with a predefined lower bound and a predefined upper bound to determine a current zone for each traffic stream selected from a set of predefined zones;
• e) comparing the current occupancy and the previous occupancy to determine whether a change in buffer occupancy for each traffic is positive, neutral or negative;
• and
• f) requesting a change in the transfer rate for a traffic stream if the zone and the change in buffer occupancy in combination meet a predetermined criteria.

An apparatus for regulating a transfer rate of traffic streams in a shared path serving a plurality of traffic streams, each traffic stream having an assigned quality-of-service index, but none of the traffic streams having a transfer rate allocation, the apparatus comprising:

• a monitor for periodically monitoring an occupancy of each traffic stream;
• a first memory for storing the occupancy of each traffic stream buffer when the occupancy is monitored;
• a second memory for storing a previous occupancy of each traffic stream buffer from a last time that the traffic stream was monitored;
• registers for storing a lower occupancy bound, an upper occupancy bound, a transfer rate increment, and a transfer rate decrement;
• and
• a circuit for determining a transfer rate change for each traffic stream using a difference between the occupancy stored in the first and second memories and a relationship of the current occupancy to the upper and lower bounds.