Graph Graph G(V, E): consists of a set V of vertices and a set E of edges Vconsists of sources sinks and other nodes A member e(u,v) of E has a capacity c(u, vto send information from u to y
Graph • Graph G(V,E): consists of a set and a set – V consists of sources, sinks, and other nodes – A member e(u,v) of E has a to send information from u to v A D S B C T V of vertices E of edges. S A B D C T 3 3 3 3 2 2 2 4 capacity c(u,v) 6
Min-Cuts and max-Flows Cuts: Partition of vertices into two sets Size of a Cut = Total Capacity Crossing the Cut Min -Cut: Minimum size of cuts 5 Max-Flows from s to t Min -Cut= Max-Flow 3 A 2 2 D 2 C
Min-Cuts and Max-Flows • Cuts: Partition of vertices into two sets • Size of a Cut = Total Capacity Crossing the Cut • Min-Cut: Minimum size of Cuts = 5 • Max-Flows from S to T • Min-Cut = Max-Flow S A B D C T 3 3 3 3 2 2 2 S 4 A D 3 3 3 2 2 B C T 3 3 2 2 4 3 2 3 2 3 2 1 7
Unicast Multicast Broadcast Broadcast Multicast communicat Unicast communicat ion Is one communicat ion is one to-a∥ ion is one- to-many. to-one
Unicast | Multicast | Broadcast Multicast Broadcast Unicast Unicast communicat ion is oneto-one. Multicast communicat ion is oneto-many. Broadcast communicat ion is oneto-all. 8
Throughput The amount of data transferred from one place to another or processed in a specified amount of time Data transfer rates for disk drives and networks are measured in terms of throughput. Typically, throughputs are measured in kbps, Mbps and Gbps
Throughput • The amount of data transferred from one place to another or processed in a specified amount of time. • Data transfer rates for disk drives and networks are measured in terms of throughput. Typically, throughputs are measured in kbps, Mbps and Gbps. 9
Wire vs wireless Wire VS Wireless WIRE WIRELESS v An edge between two nodes √ The channel of one means that the two nodes are particular edge is actually physically connected Network Modeling shared by other neighboring edge v Multicast communication is studied while network coding v Unicast communication is of multiple unicast flows remains Traffic Pattern the dominate traffic pattern a largely unknown territory v Traffic rates are varies over Y The traffic rate(or distribution) time rather than constant is predetermined and Traffic Rate do not change
Wire vs Wireless ✓An edge between two nodes means that the two nodes are physically connected. ✓Multicast communication is studied while network coding of multiple unicast flows remains a largely unknown territory. ✓The traffic rate (or distribution) is predetermined and do not change. Wire vs Wireless ✓The channel of one particular edge is actually shared by other neighboring edge. ✓ Unicast communication is the dominate traffic pattern. ✓Traffic rates are varies over time rather than constant. Network Modeling Traffic Pattern Traffic Rate WIRE WIRELESS 10