Design of scalable techniques for quality of services routing and forwarding

• US 6,738,387 B1
• Filed: 10/10/2000
• Issued: 05/18/2004
• Est. Priority Date: 06/15/2000
• Status: Active Grant

• Current Assignee: National Science Council
• Original Assignee: National Science Council
• Inventors: Hwang, Ren-Hung, Hsu, Nai-Bin, Lin, Ying-Dar
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Levitan, Dmitry
• Application Number:
  US09/685,426
• Time in Patent Office: 1,316 Days
• Field of Search: 370/229, 370/351, 370/389, 370/392, 370/395.2, 370/395.21, 370/395.4, 370/395.41, 370/395.52, 370/419, 370/428, 370/429, 709/230, 709/231, 709/232, 709/233, 709/235
• US Class Current: 370/429
• 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/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/304 Route determination for signalling traffic
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

A design of scalable techniques for Quality of Service (QoS) routing and forwarding, used to reduce the blocking probability of the flow requests, and to achieve storage and computational scalability. Three techniques have been designed: 1) an overflowed cache 2) a per-class routing mark, and 3) a two-phase routing, which can be implemented individually or simultaneously. From the evaluation results of the system simulation, show that the three scalable techniques can significantly lower the blocking probability as well as the storage and computational overheads. Such advantages make the present invention to achieve the scalability for the Quality of Services routing and forwarding.

Claims

1. A design of scalable techniques for Quality of Services (QoS) routing and forwarding, using an overflowed cache technique, wherein the forwarding cache can be divided into three parts:

a per-pair P-Cache, a per-flow O-Cache, and a per-destination D-Cache, wherein when a data or control packet arrives a QoS router, the process in which the packet is forwarded is forwarded in a process comprising;

(a) when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if the packet is a control packet, forwards it to the control module to process and update the flow state database (FSDB), refresh the flow state if the packet belongs to existing flows, otherwise, the P-Cache and the residual bandwidth database (RBDB) are examined;

(c) if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) if it is a QoS data packet, the O-Cache, the P-Cache and the D-Cache are simultaneously looked up, wherein the packet is forwarded to the next hop router according to the O-Cache entry if the O-Cache lookup is a hit, otherwise, the packet is forwarded according to the P-Cache entry if the P-Cache lookup is a hit, wherein ff the both lookups are misses, the packet is forwarded according to the D-Cache entry.

2. The design of scalable techniques for QoS routing and forwarding as defined in claim 1, wherein the P-Cache and a RBDB are examined and performs following steps, comprising:

(a) using source-destination addresses of the packet to lookup the P-Cache entries;

(b) if the P-Cache lookup is a hit, then a request bandwidth b is checked with the RBDB to ensure the QoS of the new flow, wherein if the check is successful, then the bandwidth is temporarily reserved for the new flow, and the flow will be forwarded according to the path on the P-Cache entry, on the other hand, if RBDB indicates that the residual bandwidth is not enough, the path computation function is invoked to find a QoS path based on the information in LSDB and RBDB, if a QoS path σ

is found, the forwarding information of this new flow is stored in the O-cache, which is overflowed to the O-cache, wherein if no path can be found, the flow is blocked; and

(c) if the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow, whereby the routing algorithm attempts to compute a QoS path, wherein if the path σ

is found, the algorithm stores the forwarding information in the P-cache, otherwise, it blocks the flow.

3. The design of scalable techniques for QoS routing and forwarding as defined in claim 1, wherein it also includes simultaneous use of a per-class routing mark technique, and is implemented in the following steps, comprising:

(a) when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if it is a control packet, forwards it to the control module to process and update the flow state database (FSDB), wherein in case of edge router and the flow is a new request, the C-Cache wherein O-Cache and P-Cache combination) and the residual bandwidth database (RBDB) are examined, that is, the algorithm uses the source-destination addresses of the control packet to extract the least costly feasible path π and

the index of sub-entry m from the C-Cache, wherein according to the number of sub-entries of the desired S-D pair, three cases are further discussed;

(c) if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) if it is a QoS data packet, indexing the S-D address pair and routing mark simultaneously look up the C-Cache and the D-Cache, wherein the packet is forwarded to the next hop router according to the C-Cache entry if the C-Cache lookup is a hit, otherwise, the packet is forwarded according to the D-Cache entry, wherein in case of edge router, the routing mark is retrieved from the flow state database and insert it into the packet header, then forwards the packet to the next hop router.

4. The design of scalable techniques for QoS routing and forwarding as defined in claim 3, wherein the three cases include:

(a) if the number of sub-entries of the desired S-D pair in C-Cache is empty, the lookup is missed and the algorithm attempts to compute the least costly feasible path, termed σ

, if σ

is found, the algorithm assigns a new mark to σ

, inserts it into the C-Cache, and then updates the flow state database, wherein if σ

is not found, the flow is blocked;

(b) if the number of sub-entries of the desired S-D pair in C-Cache is ‘

full’

, this algorithm simply finds the least costly feasible path π

among the existing Π

(s, d) paths, where π

∈

Π

(s, d), if π

is found, the flow is marked with the index of π

, and thus update the flow state database, if π

is not found, then blocks the flow; and

(c) if the number of sub-entries of the desired S-D, Π

(s, d), is neither empty nor full, this algorithm can either route the flow through the π

led by the C-Cache as in case 2, or route the flow through a newly computed path σ

as in case 1, whichever costs less, wherein no matter which is chosen, the flow state database is updated with the desired routing mark.

5. The design of scalable techniques for QoS routing and forwarding as defined in claim 1, wherein it also includes the simultaneous use of a path computation module and use of a two-phase routing technique, that is, when a data or control packet arrives a QoS router, the process in which the packet is forwarded, can be detailed as the following steps, comprising:

(a) first, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if the packet is a control packet, forwards it to the control module to process and update the flow state database (FSDB), refresh the flow state if the packet belongs to existing flows, otherwise, use the S-D pair addresses to lookup the P-Cache and the residual bandwidth database (RBDB) is examined;

(c) if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) if it is a QoS data packet, the P-Cache and the D-Cache are simultaneously looked up, wherein the packet is forwarded to the next hop router according to the P-Cache entry if the P-Cache lookup is a hit, otherwise, the packet is forwarded according to the D-Cache entry.

6. The design of scalable techniques for QoS routing and forwarding as defined in claim 5, wherein using the S-D address pair to lookup the P-Cache includes implementing the following, comprising:

(a) if the P-Cache lookup is a hit, and the feasibility check with RBDB is successful which means with enough residual bandwidth, then the flow will be forwarded through the path led by the P-Cache, wherein if there is not enough residual bandwidth, then the flow is blocked;

(b) if the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow, therefore, the two-phase routing technique is used to compute a feasible QoS path, wherein if the path σ

is found, the algorithm stores the forwarding information in the P-cache, otherwise, it blocks the flow.

7. The QoS route and forwarding extension design as defined in claim 5, wherein the path computation module is based on the following two-phase computation:

(a) Phase-I, referred to as soft-reservation, tries to find a path σ

₁ with greater bandwidth than the request b, that is where width(σ

₁)≧

b +b_more, wherein the b_more value can be roughly estimated and can be adjusted according to the traffic volume, path information of σ

is inserted into the P-Cache, and the soft-residual bandwidth is recorded into the soft-RBDB database, consequently, the subsequent incoming flows of the same S-D pair will be more likely to successfully reserve bandwidth on the minimum-hop path σ

₁, less misleading will increase the likelihood of success; and

(b) if a QoS path σ

₁ cannot be found, Phase-II attempts to compute a path σ

₂ with bandwidth b, that is, width(σ

₂)≧

b, referred to as hard-reservation because it considers the actual required bandwidth, path information of σ

₂ is inserted into the P-Cache, and the hard-residual bandwidth is recorded into the hard-RBDB database, if QoS path σ

₂ cannot be computed, the flow is blocked.

8. The design of scalable techniques for QoS routing and forwarding, using a per-class routing mark technique, comprising:

(a) first, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if it is a control packet, forwards it to the control module to process and update the flow state database (FSDB), wherein it is noted that in case of edge router and the flow is a new request, the C-Cache, that is, O-Cache and P-Cache combination and the residual bandwidth database (RBDB) are examined, that is, the algorithm uses the source-destination addresses of the control packet to extract the least costly feasible path π and

the index of sub-entry m from the C-Cache, according to the number of sub-entries of the desired S-D pair, three cases will be further discussed;

(c) if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) if it is a QoS data packet, indexing the S-D address pair and routing mark simultaneously look up the C-Cache and the D-Cache, wherein the packet is forwarded to the next hop router according to the C-Cache entry if the C-Cache lookup is a hit, otherwise, the packet is forwarded according to the D-Cache entry, wherein it is noted that in case of edge router, the routing mark must be retrieved from the flow state database and insert it into the packet header, then forwards the packet to the next hop router.

9. The design of scalable techniques for QoS routing and forwarding as defined in claim 8, wherein the three cases include:

(a) if the number of sub-entries of the desired S-D pair in C-Cache is ‘

empty’

, the lookup will be missed and the algorithm attempts to compute the least costly feasible path, termed σ

, if σ

is found, the algorithm assigns a new mark to σ

, inserts it into the C-Cache, and then updates the flow state database, and if σ

is not found, the flow is blocked;

(b) if the number of sub-entries of the desired S-D pair in C-Cache is ‘

full’

, this algorithm simply finds the least costly feasible path π

among the existing Π

(s, d) paths, where π

∈

Π

(s, d), if π

is found, the flow will be marked with the index of π

, and thus update the flow state database, if π

is not found, then blocks the flow; and

(c) If the number of sub-entries of the desired S-D, Π

(s, d), is neither empty nor full, this algorithm can either route the flow through the π

led by the C-Cache as in case 2, or route the flow through a newly computed path σ

as in case 1, whichever costs less, wherein it is noted that no matter which is chosen, the flow state database is updated with the desired routing mark.

10. The design of scalable techniques for QoS routing and forwarding as defined in claim 8, wherein it further includes the simultaneous use of a path computation module and use of a two-phase routing technique, that is, when a data or control packet arrives a QoS router, the process in which the packet is forwarded, can be detailed as the following steps, comprising:

(a) first, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if the packet is a control packet, forwards it to the control module to process and update the flow state database (FSDB), refresh the flow state if the packet belongs to existing flows, otherwise, use the S-D pair addresses to lookup the P-Cache and the residual bandwidth database (RBDB) is examined,

(c) if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) If it is a QoS data packet, the P-Cache and the D-Cache are simultaneously looked up, wherein the packet is forwarded to the next hop router according to the P-Cache entry if the P-Cache lookup is a hit, otherwise, the packet is forwarded according to the D-Cache entry.

11. The design of scalable techniques for QoS routing and forwarding as defined in claim 10, wherein using the S-D address pair to lookup the P-Cache includes implementing the following, comprising:

(a) if the P-Cache lookup is a hit, and the feasibility check with RBDB is successful, that is, with enough residual bandwidth, then the flow will be forwarded through the path led by the P-Cache, wherein if there is not enough residual bandwidth, then the flow is blocked;

(b) if the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow, therefore, the two-phase routing technique is used to compute a feasible QoS path, if the path a is found, the algorithm stores the forwarding information in the P-cache, otherwise, it blocks the flow.

12. The QoS route and forwarding extension design as defined in claim 11, wherein the path computation module is based on the following two-phase computation:

(a) Phase-I, referred to as soft-reservation, tries to find a path σ

₁ with greater bandwidth than the request b, that is where width(σ

₁)≧

b +b_more, the b_more value can be roughly estimated and can be adjusted according to the traffic volume, path information of σ

₁ is inserted into the P-Cache, and the soft-residual bandwidth is recorded into the soft-RBDB database, wherein consequently, the subsequent incoming flows of the same S-D pair will be more likely to successfully reserve bandwidth on the minimum-hop path σ

₁, less misleading will increase the likelihood of success; and

(b) if a QoS path σ

₁ cannot be found, Phase-II will attempt to compute a path σ

₂ with bandwidth b, that is, width(σ

₂)≧

b, referred to as hard-reservation because it considers the actual required bandwidth, path information of σ

₂ is inserted into the P-Cache, and the hard-residual bandwidth is recorded into the hard-RBDB database, if QoS path a2 cannot be computed, the flow is blocked.

13. The design of scalable techniques for QoS routing and forwarding as defined in claim 12, wherein using the S-D address pair to lookup the P-Cache includes implementing the following, comprising:

(a) if the P-Cache lookup is a hit, and the feasibility check with RBDB is successful, that is, with enough residual bandwidth, then the flow will be forwarded through the path led by the P-Cache, if there is not enough residual bandwidth, then the flow is blocked;

(b) if the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow, therefore, the two-phase routing technique is used to compute a feasible QoS path, if the path σ

is found, the algorithm stores the forwarding information in the P-cache, otherwise, it blocks the flow.

14. The design of scalable techniques for QoS routing and forwarding as defined in claim 13, wherein the P-Cache and a RBDB are examined and must perform the following steps, comprising:

(a) source-destination addresses of the packet are used to lookup the P-Cache entries;

(b) if the P-Cache lookup is a hit, then a request bandwidth b is checked with the RBDB to ensure the QoS of the new flow, if the check is successful, then the bandwidth is temporarily reserved for the new flow, and the flow will be forwarded according to the path on the P-Cache entry, on the other hand, if RBDB indicates that the residual bandwidth is not enough, the path computation function is invoked to find a QoS path based on the information in LSDB and RBDB, if a QoS path σ

is found, the forwarding information of this new flow is stored in the O-cache, that is overflowed to the O-cache, if no path can be found. the flow is blocked; and

(c) if the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow, therefore, the routing algorithm attempts to compute a QoS path, if the path σ

is found, the algorithm stores the forwarding information in the P-cache, otherwise, it blocks the flow.

15. The QoS route and forwarding extension design as defined in claim 10, wherein the path computation module is based on the following two-phase computation:

(a) Phase-I, referred to as soft-reservation, tries to find a path σ

₁ with greater bandwidth than the request b, that is where width(σ

₁)≧

b +b_more the b_more value can be roughly estimated and can be adjusted according to the traffic volume, path information of σ

₁, is inserted into the P-Cache, and the soft-residual bandwidth is recorded into the soft-RBDB database, wherein consequently, the subsequent incoming flows of the same S-D pair will be more likely to successfully reserve bandwidth on the minimum-hop path σ

₁, less misleading will increase the likelihood of success; and

(b) if a QoS path σ

₁, cannot be found, Phase-II will attempt to compute a path σ

₂ with bandwidth b, that is, width(σ

₂)≧

b, referred to as hard-reservation because it considers the actual required bandwidth, path information of σ

₂ is inserted into the P-Cache, and the hard-residual bandwidth is recorded into the hard-RBDB database, if QoS path σ

₂ cannot be computed, the flow is blocked.

16. The design of scalable techniques for QoS routing and forwarding, using a per-class routing mark technique, comprising:

(a) first, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if it is a control packet, forwards it to the control module to process and update the flow state database (FSDB), wherein it is noted that in case of edge router and the flow is a new request, the C-Cache, that is O-Cache and P-Cache combination and the residual bandwidth database (RBDB) are examined, that is, the algorithm uses the source-destination addresses of the control packet to extract the least costly feasible path π and

the index of sub-entry m from the C-Cache, according to the number of sub-entries of the desired S-D pair, three cases will be further discussed;

(c) if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) If it is a QoS data packet, indexing the S-D address pair and routing mark simultaneously look up the C-Cache and the D-Cache, the packet is forwarded to the next hop router according to the C-Cache entry if the C-Cache lookup is a hit, otherwise, the packet is forwarded according to the D-Cache entry, wherein it is noted that in case of edge router, the routing mark must be retrieved from the flow state database and insert it into the packet header, then forwards the packet to the next hop router.

17. The QoS route and forwarding extension design as defined in claim 16, wherein the path computation module is based on the following two-phase computation:

(a) Phase-I, referred to as soft-reservation, tries to find a path σ

₁ with greater bandwidth than the request b, that is, where width(σ

₁)≧

b +b_more the b_more, value can be roughly estimated and can be adjusted according to the traffic volume, path information of σ

₁ is inserted into the P-Cache, and the soft-residual bandwidth is recorded into the soft-RBDB database, wherein consequently, the subsequent incoming flows of the same S-D pair will be more likely to successfully reserve bandwidth on the minimum-hop path σ

₁, less misleading will increase the likelihood of success; and

(b) if a QoS path σ

₁ cannot be found, Phase-II will attempt to compute a path σ

₂ with bandwidth b, that is, width(σ

₂)≧

b, referred to as hard-reservation because it considers the actual required bandwidth, path information of σ

₂ is inserted into the P-Cache, and the hard-residual bandwidth is recorded into the hard-RBDB database, if QoS path σ

₂ cannot be computed, the flow is blocked.

18. The design of scalable techniques for QoS routing and forwarding as defined in claim 16, wherein it further includes using an overflowed cache technique, wherein the forwarding cache can be divided into three parts:

a per-pair P-Cache, a per-flow O-Cache, and a per-destination D-Cache, wherein when a data or control packet arrives a QoS router, the process in which the packet is forwarded is forwarded in a process comprising;

(a) first, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;

(b) if the packet is a control packet, forwards it to the control module to process and update the flow state database (FSDB), refresh the flow state if the packet belongs to existing flows, otherwise, the P-Cache and the residual bandwidth database (RBDB) are examined;

(c)i if it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and

(d) if it is a QoS data packet, the O-Cache, the P-Cache and the D-Cache are simultaneously looked up, wherein the packet is forwarded to the next hop router according to the O-Cache entry if the O-Cache lookup is a hit, otherwise, the packet is forwarded according to the P-Cache entry if the P-Cache lookup is a hit, if the both lookups are misses, the packet is forwarded according to the D-Cache entry.