A practical Network Coding and Routing Scheme based on Maximum Flow Combination
Algorithm Design for the Coding - Routing Scheme
Download 1.23 Mb.
|
- Navigate this page:
- Construction of Multicast Flow Graph
- Labelling Algorithm
- Merging Max-Flow for Obtaining Multicast Flow Graph
- The Target Set of an Edge
Algorithm Design for the Coding - Routing SchemeFirst of all, multicast flow graph is constructed by merging all the max-flow paths to every sink node. Second, all the data blocks are packed into packets along with its destination node index. Finally, these packets are dispensed from source node to sink nodes through forward, multicast or coding operations. Construction of Multicast Flow GraphMax-Flow AlgorithmsMax flow of one graph can be found out through two types of algorithm: augmenting path methods or pre-flow-push methods. Augmenting path method, also known as the Ford Fulkerson method, is based on the idea of finding out one path that could enhance the current flow, until no path could be found. Let |E| = n, |V|=m, and assume maximum edge capability is u. The general labelling algorithm is finding any possible path with the time complexity of O (nmu). The capacity scaling algorithm limited the path to be the one with maximum increasing improvement and reduces the time complexity to O (nm log u). Another shortest augmenting path algorithm - Edmonds Karp algorithm aims at finding out the path with the smallest number of nodes, e.g. the Board First Search (BFS). The time complexity is O (nm2). Labelling AlgorithmThe high level of the iterative Ford-Fulkerson-Method is described below: procedure labelling(net, s, t) initialize flow to 0 while there exists an augmenting path p augment flow along p The pseudo code of the labelling algorithm to work out the max-flow from node s to node t is described below: net[i][j] is the capacity of edge flow[i][j] is the flow value of each edge res[i][j] is the residual capacity for edge pred[i] is predecessor of node i in the augmenting path list is the set of nodes to be visited while seeking the augmenting path procedure labelling(net, s, t) begin label node t while t is labelled do begin # Find augmenting path unlabel all nodes set pred[i] ← 0 for every node i∈V label node s list ← {s} while list≠∅ or t is unlabeled do begin remove a node i from list for each edge <i,j> in the residual network do res[i][j] = net[i][j] – flow[i][j] + flow[j][i] if res[i][j]>0 and node j is unlabeled then begin pred[j] ← i label node j append j to list end end # Augment the path if t is labelled then begin use pred to trace back from t to s to obtain an augmenting path P delta := min {res[i][j] : augment delta units of flow along P end end end  
(a) (b) Max-flows to each sink node of butterfly network For example, the two max-flows to sink node 5 and sink node 6 are shown in Figure 8.(a) and (b), respectively. In this figure, flow values Fi,j and capacity values Ci,j are separated by slash “/” and placed beside each edge. The edges with non zero flow are marked with same colour with the sink node. Both sink nodes have the same maximum flow value 2. The two paths to sink node 5 are 0-1-5 and 0-2-3-4-5. Similarly, the two paths to sink node 6 are 0-1-3-4-6 and 0-2-6. Merging Max-Flow for Obtaining Multicast Flow GraphThe unit capacity of each link is a common assumption in most network coding approaches. Larger capacity is substituted with multiple parallel links in the same direction between two nodes. However, link capacity in real networks is always a quantity in a large number instead of 1. The approaches based on unit capacity encounter a problem to deal with a large number of links with unit capacity. Hence the computational complexity is increased dramatically. The proposed approach here avoids this problem. Since links are not unit capacity, the new definitions are proposed as follows. Definition 1: The merged max flow to all the sink nodes is defined as 
That is to say, for every edge, the merged max flow is the maximal one of the single max flows overlapping on the edge. The value of the merged max flow is used as the new limitation of the edge capacity. Definition 2: The overlapped edge is the edge used in two or more max-flows to different sink nodes, i.e. the edge <i, j> satisfies Fti,j >0 ∧ Fki,j>0 (1≤t≤l , 1≤k≤l, k≠t, For the example in Figure 8., the combined maximum flow for the two max-flows is shown in Figure 9.. The overlapped edges are marked with bold lines. The numbers beside the edges are the merged capacity limitations. According to Theorem 2 in Section 2, the upper bound multicast transportation capacity is the minimum one of the two single max-flows. For this example, it is min(2,2)=2, i.e. there are 2 different packets can be broadcasted from s to t1 and t2 at one time unit if network coding is used. At the end of this algorithm a network coding scheme under this capacity limitation will be constructed. The merged flow graph simplifies the network topology. Only the edges and nodes in the merged max-flows will be used to construct the coding and routing scheme, 
Merged max flows for butterfly network The Target Set of an EdgeDefinition 3: The target set of edge T is the set of all sink nodes l is the number of sink nodes For unit capacity, as  ,  is equivalent to 
For example, the target set D for butterfly network is shown in Figure 10.. It could be derived from Figure 8.. There are two sink node 5 (index=0) and sink node 6 (index=1). Edge <0, 1> is shared by both max-flows, so the target set D0,1 is {0,1}; Edge <1, 3> is on the max-flow of node 6 only, so the target set D1,3 is {1}. The other edges could be done by parity of reasoning. 
Target sets for butterfly network For multiple capacity edges, there are multiple target sets at each edge  . Each target set is defined as follows:
Intuitively, the multiple capacity edge is treated as several parallel edges, and each edge is assigned a target set. For example, if the capacity of each edge at the butterfly network is doubled. There are two target sets for each edge as shown in Figure 11.. 
Target set for double capacity edge of butterfly network Directory: dissertations dissertations -> Second Life on a Mobile Phone Nii Annan September 2011 Dissertation submitted in partial fulfilment for the degree of Master of Science in Information Technology Department of Computing Science and Mathematics University of Stirling dissertations -> Architectures for Controlling an Intelligent Autonomous Vehicle dissertations -> A historical audio and video guidebook for an Android smartphone/tablet John Reid September 2011 Dissertation submitted in partial fulfilment for the degree Download 1.23 Mb. Share with your friends:
|
is the flow value of edge <i,j> to sink node td