Router

• US 6,963,578 B2
• Filed: 07/31/2001
• Issued: 11/08/2005
• Est. Priority Date: 03/30/2001
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Aimoto, Takeshi, Akahane, Shinichi
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): SHAH, CHIRAG G
• Application Number:
  US09/917,765
• Publication Number:
  US 20020141403A1
• Time in Patent Office: 1,561 Days
• Field of Search: 370/389, 370/230.1, 370/235, 370/412, 370/413, 370/417, 370/219, 370/220, 370/225, 370/227, 370/228, 370/237, 370/429, 370/468, 370/351, 370/355, 370/356, 370/360
• US Class Current: 370/417
• 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/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers

Abstract

A router comprising a priority level distinguishing means for distinguishing the priority level of a packet by referring to the information contained in the header of the packet, a routing table where an output path comprising one or more output lines can be mapped to each level of priority, an output path determining unit that searches the routing table and determines an output path to be used for sending out packets, and a preferential delivery controller that executes delivery control in accordance with the priority level for each output line corresponding to the output path. In response to a fault state in a preferred output line, the router can reroute high priority packets over an alternative output line while maintaining priority. The router may also calculate a distribution ratio to determine the optimal load for each output line for a given packet priority.

Claims

1. A router for routing packets, each packet consisting of a header part and a data part, in accordance with a destination address that is specified in said header part, comprising:

a priority level distinguishing means for distinguishing the priority level of a packet by referring to header information in the header of the packet;

a packet distribution processing unit for determining an output line to be used for sending out packets;

a first packet transmitting unit for sending out packets over a first output line; and

a second packet transmitting unit for sending out packets over a second output line;

wherein said packet distribution processing unit determines to send out a first string of packets distinguished by said priority level distinguishing means as first-priority packets with a first destination address specified in their header part over said first output line, to send out a second string of packets distinguished as first-priority packets by said priority level distinguishing means with a second destination address specified in their header part over said second output line, and to distribute a third string of packets distinguished by said priority level distinguishing means as second-priority packets between said first output line and said second output line at a distribution ratio that is determined based on the redundant bandwidth of said first output line and the redundant bandwidth of said second output line.

2. The router as recited in claim 1, wherein said first-priority packets have a higher priority than said second priority packets.

3. The router as recited in claim 1, further comprising:

a switch for switching packets delivered from said packet distribution processing unit to one of said packet transmitting units determined by said packet distribution processing unit.

4. The router as recited in claim 1, wherein said distribution ratio is determined based on the calculated bandwidth of passed and discarded packets flowing through each of said output lines in a given period of time.

5. The router as recited in claim 1, wherein said packet distribution unit is further comprised of:

a hash value generator that generates a hash value based on information given in the header of a packet, wherein a first division of space is assigned to said first output line and a second division of space is assigned to said second output line, further wherein said hash value generator determines to send out said third string of packets over said first output line if the hash value generated by said hash value generator corresponds to the range of hash values assigned to the first division of space and said hash value generator determines to send out said third string of packets over said second output line if said hash value falls within the range of hash values assigned to the second division of said space, and further wherein a ratio between the size of said first division of space and the size of said second division of space is set in accordance with said distribution ratio.

6. The router as recited in claim 5, wherein said hash value is generated based on a combination of information given in the header part of a packet selected from the group consisting of a source address, a destination address, a source port, a destination port, a type of service, and combinations thereof.

7. The router as recited in claim 1, further comprising:

a means for observing the bandwidth used for said third string of incoming packets and determining said distribution ratio depending on the variation of the bandwidth used for said third string of incoming packets.

8. The router as recited in claim 6, further comprising:

a means for observing the bandwidth used for said third string of incoming packets and determining said distribution ratio depending on the variation of the bandwidth used for said third string of incoming packets.

9. The router as recited in claim 8, further comprising:

a first queue for queuing said third string of packets delivered from said switch and determined to be sent out over said first output line;

a second queue for queuing said third string of packets delivered from said switch and determined to be sent out over said second output line;

a first queuing control unit for determining whether said third string of packets are to be queued in said first queue or discarded without being queued in said first queue; and

a second queuing control unit for determining whether said third string of packets are to be queued in said second queue or discarded without being queued in said second queue.

10. The router as recited in claim 9, wherein said means for observing the bandwidth used for said third string of incoming packets comprises:

a first counter for counting the number of packets queued in said first queue and the number of bytes thereof as well as the number of packets discarded without being queued in said first queue and the number of bytes thereof; and

a second counter for counting the number of packets queued in said second queue and the number of bytes thereof as well as the number of packets discarded without being queued in said second queue and the number of bytes thereof.

11. The router as recited in claim 9, wherein said first and second queuing control units are one single combined queuing control unit.

12. The router as recited in claim 10, wherein said first and second counters are one single combined counter.

13. A router for routing packets, each packet consisting of a header part and a data part, in accordance with a destination address that is specified in said header part, comprising:

a priority level distinguishing means for distinguishing the priority level of a packet by referring to header information given in the header of the packet;

a packet distribution processing unit for determining an output line to be used for sending out packets;

a switch for switching packets delivered from said packet distribution processing unit to a path toward an output line determined by said packet distribution processing unit;

a first queue for queuing a first string of packets with a first destination address specified in their header part, distinguished as first-priority packets by said priority level distinguishing means delivered from said switch;

a second queue for queuing a second string of packets distinguished as second-priority packets by said priority level distinguishing means delivered from said switch;

a third queue for queuing said first string of packets delivered from said switch;

a fourth queue for queuing said second string of packets delivered from said switch;

a first packet delivery controller for reading packets from said first and second queues and for sending out the packets over a first output line; and

a second packet delivery controller for reading packets from said third and fourth queues and for sending out the packets over a second output line;

wherein said first packet delivery controller reads said first string of packets from said first queue in preference to reading said second string of packets from said second queue,

wherein said second packet delivery controller reads said first string of packets from said third queue in preference to reading said second string of packets from said fifth queue,

further wherein during normal operation said packet distribution processing unit determines to send out said first string of packets over said first output line via said first queue, and

further wherein during a fault state in said first output line said packet distribution processing unit determines to send out said first string of packets over said second output line via said third queue.

14. The router as recited in claim 13,

wherein during normal operation said packet distribution processing unit distributes said second string of packets between said first output line via said second queue and said second output line via said fourth queue at a distribution ratio that is determined based on the redundant bandwidth of said first output line and the redundant bandwidth of said second output line, and

further wherein during said fault state in said first output line said packet distribution processing unit determines to send out all of said second string of packets over said second output line via said fourth queue.

15. The router as recited in claim 14, wherein during said fault state, said first string of packets are given priority over said second string of packets over the second output line.

16. The router as recited in claim 13, wherein said packet distribution unit further comprises:

a hash value generator that generates a hash value based on information given in the header of a packet, wherein a first division of space is assigned to said first output line and a second division of space is assigned to said second output line, further wherein said hash value generator determines to send out said second string of packets over said first output line if the hash value generated by said hash value generator corresponds to the range of hash values assigned to the first division of space and said hash value generator determines to send out said second string of packets over said second output line if said hash value falls within the range of hash values assigned to the second division of said space, and further wherein a ratio between the size of said first division of space and the size of said second division of space is set in accordance with said distribution ratio.

17. The router as recited in claim 16, wherein said hash value is generated based on a combination of information given in the header part of a packet selected from the group consisting of a source address, a destination address, a source port, a destination port, a type of service, and combinations thereof.

18. The router as recited in claim 14, further comprising:

a means for observing the bandwidth used for said second string of incoming packets and determining said distribution ratio depending on the variation of the bandwidth used for said second string of incoming packets.

19. The router as recited in claim 18, wherein said means for observing the bandwidth used for said second string of incoming packets comprises:

a first counter for counting the number of packets queued in said second queue and the number of bytes thereof as well as the number of packets discarded without being queued in said second queue and the number of bytes thereof; and

a second counter for counting the number of packets queued in said fourth queue and the number of bytes thereof as well as the number of packets discarded without being queued in said fourth queue and the number of bytes thereof.

20. A method of routing packets in a network, comprising the steps of:

sending a high priority string of packets via a first queue over a first output line;

sending a low priority string of packets via a second queue over said first output line and via a third queue over a second output line;

detecting a fault in said first output line;

rerouting said high priority string of packets over said second output line via a fourth queue, wherein packets sent from the first queue and the fourth queue have priority over the packets sent from the second queue and the third queue respectively.