System and method for network flow optimization using traffic classes

• US 6,262,976 B1
• Filed: 09/17/1999
• Issued: 07/17/2001
• Est. Priority Date: 09/17/1998
• Status: Expired due to Fees

• Current Assignee: Ordered Networks, Inc.
• Original Assignee: Ordered Networks, Inc.
• Inventors: McNamara, Tod W.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/398,663
• Time in Patent Office: 669 Days
• Field of Search: 370/229, 370/231, 370/235, 370/238, 370/254, 370/255, 370/351, 370/352, 370/389, 370/400, 370/401, 370/428, 709/201, 709/220, 709/230, 709/238, 709/242, 710/104, 710/105, 710/131
• US Class Current: 370/254
• 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/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

Disclosed are methods of routing traffic through a network with a plurality of nodes which comprises classifying network traffic into a plurality of classes, including interior, interior-to-exterior, exterior-to-interior, and transitory. At each node of the network, a packet, designated as belonging to a traffic class and including a source node address and a destination node address, is received. The packet is indexed into the node'"'"'s packet switch matrix using the traffic class designation, source node address, and destination node address to obtain a node link number for forwarding the packet. Then, the packet is forwarded upon a link indicated by the node link number.

Claims

1. In a network including a plurality of switches, hosts and links connecting said switches and hosts into a topology, a method of ordering said network comprising:

dividing said switches into two classes, interior and exterior, wherein said interior class switches only have links to other switches and hosts within said network, and exterior class switches have at least one link to other networks or entities outside of said network;

within said interior class, determining a central switch within said interior class, said central switch determined by having the most links to other interior switches;

determining an ordering of all switches in said interior class, based on number of links to other interior switches, starting from said determined central switch;

determining an ordering of all switches in said exterior class, based on number of links to interior switches;

starting from 1 greater than the number of interior class switches;

for each switch, ordering all links connected to that switch by said ordering of said interior and exterior class switches, wherein a link to a switch with a lower ordering number will precede a link to a switch with a higher ordering number; and

numbering said ordered links from 1 up to total number of links connected to that switch.

2. The method of claim 1 wherein traffic on said ordered network is routed on a link of a switch based on said numbering of links out of said switch, and a classification of said traffic.

3. The method of claim 2 wherein traffic on said ordered network is divided into one of a plurality of classes, including interior traffic, interior-to-exterior, exterior-to-interior, and transitory.

4. The method of claim 3 wherein traffic in said ordered network that is classified as interior traffic will be routed out of said switch links with a low link number.

5. The method of claim wherein traffic in said ordered network that is classified as transitory traffic will be routed out of said switch on links with a highest link number.

6. The method of claim wherein said method is performed by one switch in said network, and said resulting link numbering for each switch in said network.

7. A method of routing traffic through a network having a plurality of nodes, comprising:

classifying network traffic into a plurality of classes, including interior, interior-to-exterior, exterior-to-interior, and transitory;

at each node in said network, upon receiving a packet designated as belonging to a traffic class and including a source node address and a destination node address, indexing into said node'"'"'s packet switch matrix using said traffic class designation, source node address, and destination node address to obtain a node link number for forwarding said packet; and

forwarding said packet upon a link indicated by said node link number.

8. The method of claim 7 wherein:

packets designated as interior traffic are routed through topologically interior nodes of said network;

packets designated as transitory traffic are routed through topologically exterior nodes of said network;

packets designated as interior-to-exterior traffic are routed through topologically interior nodes towards topologically exterior nodes of said network; and

packets designated as exterior-to-interior traffic are routed through topologically exterior nodes towards topologically interior nodes of said network.

9. The method of claim 7 wherein each packet includes a header which includes said particular traffic class of said packet, said source node address, and said destination node address.

10. The method of claim 9 wherein said header is a four-byte header in identical format to standard IP address headers.

11. The method of claim 10 wherein:

said second byte of said four-byte packet header indicates said traffic class designation;

said third byte of said four-byte packet header indicates said source node; and

said fourth byte of said four-byte packet header indicates said destination node.