Research Of Link-State Updating Mechanism In QoS-based Routing

Traditional data networks were designed to provide best-effort service. This service is suitable only for data communication applications such as ftp, telnet etc. With the recent developments in transmission and computing technologies, distributed multimedia applications such as video conferencing have now become possible and will be widely used in the near future. Such applications transmit information which usually has different traffic characteristics and various QoS performance requirements, similar to the case of real-time communication. To support the requirements of such applications, the underlying network must provide certain levels of quality-of-service(QoS)while simultaneously maintaining efficient use of network resources. The goal of QoS routing is to identify a resource-efficient, feasible path that satisfies a set of constraints. QoS routing involves two basic tasks: (1) capturing the state of the available network resources and disseminating this information throughout the networks; (2) computing a feasible and optimal path which satisfies the QoS requirements of request flows. The QoS routing has not been solved yet because of the following three difficulties: (1) The dynamics of network link state information, (2) It is a NP-hard problem to find a feasible path which satisfies multiple QoS metrics at the same time if not impossible. (3) Combining current best-effort routing with QoS routing. Most current research focus on the second task and the second difficulty of QoS routing problem. However, few attention has been concentrated on the first task and the first difficulty of QoS routing problem. The main work of this paper is to study the link state dissemination mechanism of the first task of QoS routing problem and put forward two new link state updating methods. QOSPF is the QoS extension of link state routing protocol OSPF. It is studied and analyzed in this paper. The main extension of QOSPF include: identification of supporting QoS, containing and encoding of QoS metrics, triggering mechanisms of link state updating, Qos routing algorithms with bandwidth constraint and so on. It is required to update link state information frequently in QoS routing for accurate input of Qos routing algorithms. In QOSPF, several update triggering mechanisms were discussed, however, flooding updating method is still adopted in QOSPF. It is obvious that frequent flooding will result in magnificent communication overhead. The LSAs containing QoS metric information will waste network bandwidth, consequently the call accepting ratio will be reduced. It is difficult to find the balance between link state updating frequency and link state information accuracy. In this paper, two link state updating mechanisms are presented: FBLT for stable network environment and IFBLT for dynamic changing network environment.With these two updating mechanisms, we can get accurate link state information without too huge communication overhead. The main idea of FBLT mechanism is as follows: introducing the idea of source-based tree into flooding mechanism, namely, when a new period starts, set up a link state updating tree for every node in the network by flooding the first LSA, Afterwards, the LSAs will be disseminated along the LSU tree. No complicated protocol or algorithm is needed to set up these LSU trees in this paper. According to the LSA acknowledgement mechanism in OSPF, each LSA should be retransmitted unless acknowledged. In this paper, A TF (tree mode or flooding mode) bit is extended of the LSA packet's Option field in this paper, which can be set to 1 in the acknowledgement packet to build parent-children relationship between two nodes. According to this method, every node is joind up to the LSU tree gradually, the LSU tree built is actually the least-delay tree from the LSA originator to all the other nodes because the node only set TF=1 when sending acknowledgement to the sender of the latest and first LSA. During the period, the LSAs are disseminated along this least-delay tree, which can save the wasting of bandwidth because of repeatedly forwarding the same LSA to the same node. FBLT scheme has a defect. Partial nodes can not receive LSA for Link failure occurrence. This paper has put forward 3 kinds of solutions according to this problem, based on the change minimum principle, the third scheme of IFBLT is given detailed discussion. It adds the dynamic repairing procedure to FBLT for...