Problem 1 outing vs. Network Coding Consider the six-node directional network de

Question

Problem 1 outing vs. Network Coding Consider the six-node directional network depicted in Figure 1 where flows a and b are to be transferred to both destination nodes E and F (called multicast). Assume all links to have the same maximum data rate R 1. Figure 1: Network coding. 1. Suppose all nodes forward the data flows and no operation (e.g., computation) on their content is allowed. A flow may take multiple routes. If flows a and b are equal in data rate, find the maximum flow (maximum rate of a and b) that can be handled by the network. 2. In the paper "Network Information Flow by R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, which was published on the IEEE Transactions on Information Theory in 2000, a new paradigm is proposed where the intermediate nodes are allowed to operate on the data. The paper pioneered an active research area called network coding. Suppose all nodes are allowed to do XOR (i.e., addition modulo 2) the incoming flows, what is the maximum flow that can be handled by the network if flows a and bare equal (the answer should be greater than that of question (1))? How?

Explanation / Answer

1) so as already said in question data rate is same between all paths of a and b.. so we can have maximum flow...

that is longest path required toreach b from a.

So maximum flow is either these two paths....[ a->A->C->F->E->b or   a->A->C->F->D->a ]

2) yes, if two nodes are XOR ed with each other ..then bandwidth is reduced to half....and this calculated bandwidth is saved...so on every xor with every node will lead to reduce bandwidth by half....this will lead to make a node multicast node....which makes maximum flow automatically increases rather than normal calculation of max flow.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.