DOC PREVIEW
Chico CSCI 693 - Quickest path and Quickest routing: A dynamic routing method

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

I. INTRODUCTIONAbstract— Most routing protocol based on shortest path etc. Such kind of protocol could not balance traffic automatically. QP has such property that automatically distribute traffic depend on the data amount transferred. In this paper a quickest routing algorithm protocol called conflict free optimal quickest path protocol will be presented. This algorithm can utilize multiple paths. It also can further reduce network traffic congestion. Index Terms—Algorithm, congestion control, network protocol, quickest path, routingI. INTRODUCTIONITH rapidly developed high speed network and increasingly demand on multimedia, military and distribute data retrieval, quickly and reliable transport data package is a kernel issue of world wide network. Many data transport protocols have been developed and employed in use for distributed data intensive applications over wide area high-speed networks. OSPF (open shortest path first) and IS-IS (intermediate system-intermediate system) all use shortest path algorithm as decision policy. These protocols are good but less efficiency to balance traffic distribution, breaking the data transfer bottleneck and resolve data congestion problem. W In this paper we will propose a network routing protocol called local optimal quickest path routing protocol which is based on quickest path concept. The quickest path protocol is based on the theory of quickest path problem which is a variant of shortest path problem. And we also provide a conflict free optimal quickest path algorithm. In section II will introduce the quickest path. In section III will discuss related work and network protocols. In section IV discusses QP algorithm for all any value of m. Section V discusses the local optimal quickest routing solution. Section VII provides a conflict free data Quickest path and Quickest routing: A dynamic routing method Research Topic: Jiang, XidongMS candidate in computer science at California State University, Chico, CA 95929-0410 USA (e-mail: [email protected])splitting quickest path algorithm. Section VII is brief discussion and further work. Section VIII is the conclusion. II THE QUICKEST PATH PROBLEM OVERVIEW The quickest path problem (QPP), an optimal problem, was initially from Chen and Chin [1]. In the past 2 decades, the QPP has got a lot attention since it published. A lot associate QP problems emerged. Given a network N, denote N = (V, E, c, l, s, t), where G = (V, E) is simple connected directed graph. A simple graph G means G without multiple arc (edge) and self loops. V is node set of G and E is edge set of G. c(u, v) ≥ 0 is the capacity of an edge (u, v) ϵ E. l (u, v) ≥ 0 is a lead time or time delay of travel time of a packet passing though an edge (u, v) ϵ E. s is the source that sends data packet. And t is the destination node that receives data. More generality c(u, v) is a unit time the maximum transport amount of data from node u to node v by edge of (u, v). Given certain amount of data packet m, we want the m unit of data to be transferred from s to t in a shortest time. Let p is a path with k-1 arc (ui, ui+1) ϵ E from s to t. denoted as p = (s= u1, u2,…, uk = t), p ϵ Ƥ = { p | p is the path from s to t}. The lead time of traversal delay of path p is l(p) = ∑−=+111),(kiiiuulThe capacity of path p is c(p) = min {c(iu,1+iu)|(iu,1+iu) ϵ pEof sub set of E}To any m unit data requires transmission time from s to t is T.T = l(p) + )( pcm (1)The quickest path from s to t is the path that with the minimum time T. If p is quickest path,T (p) = min +c(p)m l(p) = min {∑−=+111),(kiiiuul + )},(min{1+iiuucm} (1) Is the basic formula of QP, now lets stick on this concept of [1, 2, 3, 4] etc that all QP problem (QPP) have been discussed so far as above. Convert to network language it can be described as a pass and forward routing. In order to fully understand the difference QPP with SPP and deeply analysis the QPP, the following will present the properties of QP. It is important to notice that the value or the property of (1) more related with m and c(p).Let G as graph defined as above, p is a QP of G. Let put two observations [1~4] followas. Observation 1: To any graph G, p is QP of G to transmit m unit volume of data, the sub path of p could not maintain the property that the sub QP is QP of G. Observation 2: To any graph G, the QP is function of f (m, c, l), in a c and l are given graph G, QP is m dependent. iFigure 1. Example of the sub path of QP is not a sub QP of GFigure 1 and figure 2 show the observation 2. T p1 p2 p3 pathm abe ace ade QP20 34 37 40 p160 42 41 45 p2100 50 45 44 p3c=5,L=30 c=10,L=35 c=20,L=39T p1 p2 p3 pathm abef acef adef QP20 40 45 45 p160 50 55 47 p2100 60 65 49 p3c=4,L=35 c=4,L=40 c=4,L=44Figure 2: the relationship the QP and data sizeT sub p1 p1 sub p2 p2 sub p3 p3 pathm abe abef ace acef ade adef QP20 34 40 37 45 40 45 p160 42 50 41 55 45 47 p2100 50 60 45 65 44 49 p3c=5,L=30 c=4,L=35 c=10,L=35 c=4,L=40 c=20,L=39 c=4,L=44Figure 3. QP sub path is not maintain as sub QP[1] provides QP algorithm for given value m as (1). Article [1] also provides QP algorithm for all value of m. Noticed that with different value m the QP path is different. To any value m [1] give a QP algorithm. For a any big value M, Partition let m1<m2,…,mk = M. The algorithm gives a set of path p1, p2, …pk. The data value and path set is P = {( m1, p1), (m2, p2),…(mk , pk )}. Based on above property of QP and the work of [1] we will provide a new QP protocol in section VII. III RALATED WORKIn [5] Hung discussed that how to find quickest routing path for multimedia data. He discussed the constrained quickest path problem. The constrained quickest path is not any available quickest path. It is “the quickest paths are required to go through a specified path, then therestricted problem is called the constrained quickest path problem” [5]. His contribution is to provide a few new distributed routing algorithms for multimedia data transfer in an asynchronous communication network. Article [6] is one of the papers that apply quickest path concept to network routing study. Authors discussed the K-quickest paths to the routing of data packets in Internet networks. In this paper author apply k-quickest path problem to


View Full Document

Chico CSCI 693 - Quickest path and Quickest routing: A dynamic routing method

Download Quickest path and Quickest routing: A dynamic routing method
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quickest path and Quickest routing: A dynamic routing method and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quickest path and Quickest routing: A dynamic routing method 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?