Packet routing system and method therefor

In a communication system comprised of nodes that communicate with each other over links, a method of routing data packets among said nodes comprising the steps of:

• (a) predicting an actual traffic load during a planning interval to determine an anticipated system traffic load during said planning interval, said planning interval being a predetermined period of time;
• (b) partitioning said anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;
• (c) providing a routing instruction set for each node for one of said traffic levels;
• (d) performing a routing simulation using said initial routing instruction set and traffic loading of said one traffic level;
• (e) finding overloaded links by comparing a link capacity of each of said links with a utilized capacity of each of said links during said routing simulation;
• (f) performing a second routing simulation using traffic loading of said one traffic level excluding links determined to be overloaded from step (d);
• (g) generating a new routing instruction set based on said second routing simulation, said links determined to be overloaded being excluded from said new routing instruction set;
• (h) repeating steps (e) through (g) until no links are overloaded;
• (i) repeating steps (c) through (h) for each of said traffic levels;
• (j) repeating steps (a) through (i) for subsequent planning intervals;
• and
• (k) generating a routing table for each of said nodes, said routing table comprising said new routing instruction set for each of said traffic levels
• (l) routing said data packets away from one of said nodes according to said routing table for said one node.

In a communication system comprised of nodes that communicate with each other over links, a method of routing data packets among said nodes wherein said data packets include a destination routing code, the method comprising the steps of:

• (a) partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;
• (b) providing a routing instruction set for each node for one of said traffic levels;
• (c) performing a routing simulation using said routing instruction set and traffic loading of said one traffic level;
• (d) finding overloaded links by comparing a link capacity of each of said links with a utilized capacity of each of said links during said routing simulation;
• (e) performing a second routing simulation using traffic loading of said one traffic level excluding links determined to be overloaded from step (d);
• (f) generating a new routing instruction set based on said second routing simulation, said links determined to be overloaded being excluded from said new routing instruction set, said new routing instruction set associating said destination routing code with an exit link of each of said nodes;
• and
• (g) routing said data packets away from one of said nodes according to said new routing instruction set.

A method of routing a data packet among nodes in a constellation of nodes coupled by links, said nodes being part of a communication system wherein said data packet includes a destination routing code that indicates a destination node for said data packet, said method comprising the steps of:

• receiving said data packet at one of said nodes;
• reading said destination routing code from said data packet;
• reading a connection identification (ID) from said data packet;
• reading least significant bits (LSB) from said connection ID;
• indexing a routing table stored in said one of said nodes based on said connection ID and said destination routing code;
• determining an exit link of said one node by reading said routing table;
• and
• routing said data packet away from said one node over said exit link, and
• wherein said routing table being generated by the steps of:
• partitioning an anticipated system traffic load of said communication system into traffic levels, each traffic level being a subset of said anticipated system traffic load;
• generating an initial routing instruction set for each node for one of said traffic levels;
• determining if any of said links will be overloaded based on said initial routing instruction set;
• re-generating, when said any of said links are determined to be overloaded, said routing instruction set for each node by excluding said links determined to be overloaded;
• repeating the re-generating and determining steps until no links are determined to be overloaded;
• repeating the generating step, the determining step and the re-generating step for each of said traffic levels;
• and
• generating said routing table for each of said nodes, said routing table comprising said routing instruction set for each of said traffic levels,
• and wherein said indexing step includes the step of pointing to one of several portions of said routing table based on said LSB, each portion of said routing table being associated with one of said traffic levels.

A method of recursively determining routing for data packets in a communication system comprised of nodes connected by links, said method comprising the steps of:

• (a) partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;
• (b) generating an initial routing instruction set for each node for one of said traffic levels;
• (c) determining if any of said links will be overloaded based on said initial routing instruction set;
• (d) re-generating, when said any of said links are determined to be overloaded, said routing instruction set for each node by excluding said links determined to be overloaded
• (e) repeating the re-generating and determining steps until no links are determined to be overloaded;
• (f) repeating steps (b), (c) and (d) for each of said traffic levels;
• (g) generating a routing table for each of said nodes, said routing table comprising said routing instruction set for each of said traffic levels;
• and
• (h) sending said routing table for each of said nodes to said each node
• wherein said step (a) partitions said anticipated system traffic load into traffic levels for each of a plurality of planning interval, said planning intervals, each planning interval being a predetermined period of time, said plurality of planning intervals comprising a planning period, and
• wherein said method further comprises the step of repeating steps a through g for each of said planning intervals in a planning period, said planning interval being between fifteen seconds and one minute, said planning period being approximately twenty-four hours.

A communication system that routes a data packet comprising:

• a plurality of nodes that move with respect to each other, said nodes coupled by communication links;
• transceivers associated with each node of said plurality of said nodes for routing said data packet over said communication links;
• a memory for storing a routing table;
• a first processor for generating said routing table;
• and
• a second processor for reading said routing table and instructing said transceivers to send said data packet away from one of said nodes based on said routing table, and said first processor comprising:
• means for partitioning an anticipated system traffic load into traffic levels, each traffic level being a subset of said anticipated system traffic load;
• means for generating a routing instruction set for said one of said nodes for said traffic levels;
• means for determining if any of said communication links will be overloaded based on said routing instruction set;
• and
• means for re-generating, when said any of said communication links are determined to be overloaded, said routing instruction set for said one of said nodes by excluding said communication links determined to be overloaded.