Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
2000-10-10
2004-05-18
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Store and forward
C370S392000, C709S232000
Reexamination Certificate
active
06738387
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a design of scalable techniques for Quality of Services (QoS) routing and forwarding. More particularly, the present invention relates to a use of a design of scalable techniques for QoS routing and forwarding.
2. Description of the Related Art
The next generation of the Internet must provide users with diverse, fine-grain, and subjective QoS functions, particularly in light of the increasing demand for a wide spectrum of network services. Even though Resource ReSerVation Protocol (RSVP) can reserve resources for individual flows (that is, an IP packet stream between the same source-destination (S-D) pair of the session), however, current Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) protocol always find the shortest paths, and do not consider the bandwidth or other the limitations of the link. Consequently, the path may not have enough resources to provide the QoS for the flow request. In this way, RSVP reservation from the receiver could be blocked. That is, RSVP can work with RIP or OSPF to provide QoS to individual flows, however, probably with a substantially high blocking probability. Also, whenever the per-destination entry of the routing table is updated, the next hop of the associated route may be changed immediately, possibly interrupting the QoS of the flow forwarded on that path.
To reduce the blocking probability and keep stable provision during the session of a flow, QoS routing is highly desired in integrated services networks. QOSPF routing mechanism of the IETF is QoS extensions to the current OSPF, thus providing QoS path computation. During computation, QOSPF takes link bandwidth into account and the results are stored on the QoS routing table, and is used to lookup the path of a new flow request (e.g., new PATH messages of RSVP).
Moreover, for route pinning, routers can avoid oscillation and facilitate wire-speed forwarding of packets by using a forwarding cache, to record the forwarding decisions. In this way, routers usually do not need to query the QoS routing table upon packet arrival. In addition, the cache pins the forwarding path to avoid frequent change(s) which may interrupt the QoS provision.
Among the factors that affect the QoS routing performance and efficiency, granularity of the routing decision significantly affects the scalability and the blocking probability. In present day, different routing techniques use different granularities. For example, OSPF has the coarsest granularity and uses per-destination routing entries. As a request, all flows moving from different sources to a destination are forwarded to the same outgoing link on the same router. Moreover, routing granularity of MOSPF and a version of QOSPF are per-pair, i.e. based on source and the destination addresses of routed flows. In that way, all traffics of a given source and a given destination, regardless of the number of flows, travels the same route. Among the other QoS routing algorithms, such as PQC and alternate path routing, have the finest granularity, i.e per-flow. Each individual flow is routed independently.
Per-pair cache entries could result in misleading, i.e., flows following a cache entry might not find sufficient resources along the path while other paths with abundant resources still exist. This lack of resources is attributed to that flows of the same node pair use the same entry computed merely for the first existing flow between the node pair. Therefore, this path might not satisfy the bandwidth requirements of subsequent flows. Notably, the blocking probability increases when a link along the path becomes a bottleneck. On the other hand, although no such misleading occurs in the per-flow routing the cache size could be enormous. Poor scalability would ultimately result. Furthermore, due to the overhead of per-flow path computation, on-demand path-finding is hardly feasible in real networks. Therefore, path pre-computation is implemented in a version of QOSPF, which provides the results of computational cost and protocol overhead in QoS routing. In sum, QOSPF has the strength in low blocking probability and scalability in path computation. However, in wire-speed forwarding routers, per-flow forwarding of QOSPF loses storage scalability, from the perspective of the size of the forwarding cache.
SUMMARY OF THE INVENTION
The invention provides three scalable techniques for QoS routing and forwarding: 1) Overflowed cache technique-the mechanism provides three different granularities within the routing/forwarding cache. 2) Per-class routing mark technique—the mechanism computes several alternate routes between each source-destination (S-D) pair. 3) Two-phase routing technique—this mechanism provides a soft-reservation concept in order to reduce the misleading probability in the per-pair routing/forwarding cache. Hence, these QoS routing techniques not only routes data flows with quality of services (QoS), but also fast forwards data packets, reduces the blocking probability, and achieves storage and computational scalability.
As embodied and broadly described herein, the invention provides a design for a Quality of Services routing and forwarding with scalability, which includes three techniques: overflowed cache, per-class routing mark and two-phase routing, wherein the three techniques can be simultaneous or individual implemented.
The cache of the overflowed cache technique can be divided into three parts: a per-pair P-Cache, a per-flow O-Cache, and a per-destination D-Cache. 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:
1. 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;
2. 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;
3. 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
4. If it is a QoS data packet, the O-Cache, the P-Cache and the D-Cache are simultaneously looked up. 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 both lookups are misses, the packet is forwarded according to the D-Cache entry.
The above-described examines the P-Cache and the RBDB must perform the following steps:
1. Source-destination addresses of the packet are used to lookup the P-Cache entries;
2. 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 v is found, the forwarding information of this new flow is stored in the O-cache, i.e. overflowed to the O-cache. If no path can be found, the flow is blocked;
3. 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 &sgr; is found, the algorithm stores the forwarding information in the P-cache. Otherwise, it blocks the flow.
As for the per-class routing mark technique, its implementation is as follows:
1. First, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identif
Hsu Nai-Bin
Hwang Ren-Hung
Lin Ying-Dar
J.C. Patents
Kizou Hassan
Levitan Dmitry
National Science Council
LandOfFree
Design of scalable techniques for quality of services... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Design of scalable techniques for quality of services..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Design of scalable techniques for quality of services... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3216765