Method for achieving high-availability of itineraries in a real-time network scheduled packet routing system

• US 8,477,616 B1
• Filed: 01/16/2003
• Issued: 07/02/2013
• Est. Priority Date: 06/05/2001
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Greenwald, Joseph, Moore, Sean, Rogers, Steven, Ball, Scott
• Primary Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US10/345,897
• Time in Patent Office: 3,820 Days
• Field of Search: 370/395.4, 370/395.41, 370/395.42, 370/395.31, 370/248, 370/252, 370/254, 370/389, 370/395.51, 370229-238, 711/216, 711/221
• US Class Current: 370/235
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/33 using forward notification
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/829 Topology based
• CPC Class Codes: H04L 49/206 Real Time traffic
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports

Abstract

A system using scheduled times for transmission at each link guarantees bandwidth for transmitting data across a packet network. A scheduling agent determines availability of data paths across a network according to pre-selected criteria and real-time network topology information. Precise schedules are determined for transmission and reception appointments for data packets to traverse each link and switch in the network including compensation for transmission delays and switch latencies, resulting in a fixed packet flow itinerary for each connection. Itineraries are communicated to schedule-aware switches and endpoints and appointment times are reserved for transmission of the scheduled data packets. Scheduled packets arriving at each switch are forwarded according to their predetermined arrival and departure schedules, rather than their headers or contents, relieving the switches from making real-time routing decisions. Any unscheduled transmission times remain available for routing of unscheduled packets according to their IP headers. Real-time transmission of data can be guaranteed in each scheduled path, and schedule selection criteria may be adjusted according to network utilization and tolerable setup delay and end-to-end delay.

Claims

1. A method for scheduling real time data across a network comprising the steps of:

collecting information about network topology including path information and appointment information;

using said path information to identify a set of possible paths across a network to satisfy a connection request;

for each path from said identified set, examining appointment slots along said path to determine if at least one complete path can be traversed using available appointments having an acceptable cumulative phase-shift, wherein said phase-shift is a difference, measured across each switching and transmission element between communicating endpoints, in a dimension selected from one or more of;

frequency, flow mass, time-frequency, flow type, packet type, and packet mass, and wherein said phase shift is not related to packet jitter;

until either a complete path is determined or said identified set of possible paths is exhausted;

publishing an itinerary to each path element if said at least one complete path has been determined;

or

rejecting said connection request if said identified set of possible paths has been exhausted without determining at least one complete path.

2. The method of claim 1 in which said cumulative phase-shift is acceptable if it falls below a limit selected according to one or more of:

pre-configured for a network or for an end-point, configured according to connection request blocking probability requirements, network size, maximum allowable connection setup time, and available resources.

3. The method of claim 2 in which said available resources depend upon buffers in one or more of said path elements.

4. The method of claim 1 in which said acceptable cumulative phase shift is adjusted according to a measurement of network utilization.

5. The method of claim 1 in which said acceptable cumulative phase shift is adjusted according to the number of requests being rejected.

6. The method of claim 1 in which said step of examining appointment slots further comprises the steps of:

obtaining a sequenced list of appointment schedules for each element along said path;

for each said appointment schedule in said sequenced list,

selecting a first appointment in said schedule available to handle a packet after a predetermined time, and rejecting said path if no appointment is available in said schedule within less than an acceptable phase-shift limit;

until an appointment is selected for each element in said sequenced list.

7. The method of claim 6 in which said predetermined time is calculated according to whether an element in said sequenced list is a receiving interface or a transmitting interface of a scheduled network switch.

8. The method of claim 1 in which said step of examining appointment slots further comprises the steps of:

obtaining a sequenced list of appointment schedules for each element along said path;

for each said appointment schedule in said sequenced list,

selecting a first appointment available to handle a packet after a predetermined time,

queuing a request for said first available appointment if no acceptable appointments are currently available for said element;

selecting said first available appointment if it becomes available within a predetermined time after queuing said request; and

rejecting said path if no appointment within less than an acceptable phase-shift limit is available in said schedule after expiration of said predetermined time;

until an appointment is selected for each element in said sequenced list.

9. The method of claim 1 in which said phase-shift is a difference in time measured across each switching and transmission element between communicating endpoints.

10. A method for scheduling real time data across a network comprising the steps of:

identifying a set of possible paths across a network to satisfy a request;

using predetermined graph traversal methods to search the identified set for available packet handling appointments until an available appointment path is found, or until predetermined halting criteria are reached, wherein said search includes, for each path from said identified set, examining appointment slots along said path to determine if at least one complete path can be traversed using available appointments having an acceptable cumulative phase-shift;

until either a complete path is determined or said identified set of possible paths is exhausted;

and if said identified set of possible paths has been exhausted without determining at least one complete path then rejecting said request;

whereby search of said set of possible paths is constrained according to criteria derived from link utilization, network topology, and availability;

wherein said phase-shift is a difference, measured across each switching and transmission element between communicating endpoints, in a dimension selected from one or more of;

frequency, flow mass, time-frequency, flow type, packet type, and packet mass, and wherein said phase shift is not related to packet jitter;

configuring said available appointment path, if one was found; and

rejecting said request if said halting criteria are reached.

11. The method of claim 10 in which said predetermined graph traversal method is selected from one or more of:

breadth-first-search approach, branch-and-bound search approach, and depth-first-search approach.

12. An apparatus for forwarding packets at precise times in a packet switching system comprised of:

a set of connected routers;

each router configured for precise switching using packet ingress time on a port to index entries in a forwarding table;

said entries containing forwarding information including egress port and egress time for each scheduled packet flow;

and wherein the router will transmit each scheduled packet on said egress port at the egress time indexed by the ingress time for said flow;

where said forwarding table entries are populated according to a network scheduling algorithm in which phase shift between said ingress time and said egress time is limited according to predetermined criteria influenced by system utilization and tolerance for delay in said flow, wherein said phase-shift is a difference, measured across each switching and transmission element between communicating endpoints, in a dimension selected from one or more of;

frequency, flow mass, time-frequency, flow type, packet type, and packet mass, wherein said phase shift is not related to packet jitter.

13. The apparatus of claim 12 further comprised of:

a schedule agent for collecting and managing router connection information and available ingress and egress times on each port on each router; and

at least one end-point device for requesting a connection across said packet switching system;

wherein said schedule agent receives requests from end-point devices and carries out said scheduling algorithm to determine a path by which a flow of packets can be transported via a series of available ingress times and egress times on available ports of each of said connected routers forming part of said path.

14. The apparatus of claim 12 in which said routers are configured to carry unscheduled data packets using ingress and egress times that have not been reserved for any of said schedule flows.

15. The apparatus of claim 12 in which each connected router is in communication with at least one schedule agent for the purpose of providing information in the set of:

network topology, neighbor status, port status, schedule tables, schedule reports, end-point requests, and event reports; and

for the purpose of receiving information in the set of;

itinerary identifiers, interface indices for incoming and outgoing flows;

flow type and length;

max packet size;

indicators for which appointments to receive and transmit packets, buffering delay parameters, and branching indicators.

16. The apparatus of claim 12 in which said scheduling algorithm further includes:

means for marking ingress and egress times as either reserved or available;

means for selecting and reserving a set of said times in response to a connection request;

means for selecting only times marked as available for subsequent connection requests;

means for rejecting connection requests for which a set of available times cannot be found within predetermined selection criteria; and

means for adjusting said selection criteria in response to system utilization measurements.