通信网理论基础（工程硕士）：Broadband Communication Networks

1、Broadband Communication Networks考试时间和地点通信网理论基础2班开卷2015/1/13上午 8:0010:00张琳3-117(信通)、3-130（电子、光研、网研）145宽带通信网（2014级信通院留学生）开卷2015/1/20下午 14:0016:00张琳3-20711-What we have doneKnown and unknown（Feb., 12， 2002, Donald Rumsfeld ）As we know, There are known knowns. There are things we know we know. We also k

2、now There are known unknowns. That is to say We know there are some things We do not know. But there are also unknown unknowns, The ones we dont know We dont know. “据我们所知，有已知的已知，有些事，我们知道我们知道；我们也知道，有 已知的未知，也就是说，有些事，我们现在知道我们不知道。但是，同样存在未知的未知有些事，我们不知道我们不知道。” 10/1/20224已知与未知:美前国防部长拉姆斯菲尔德回忆录美国历史上最年轻的国防部长（

3、 1975-1977年 ），到最年长的国防部长（ 2001-2006年 ），7 Layer OSI Reference Model10/1/20225ch2: Point-to-Point Protocols and Links The Data Link Layer: ARQ ProtocolsARQ (Automatic Repeat ReQuest)When the receiver detects errors in a packet, how does it let the transmitter know to re-send the corresponding packet?Sy

4、stem which automatically request the retransmission of missing packets or packets with errors are called ARQ systemscorrectness: Does the protocol succeed in releasing each packet, once and only once, without errors, from the receiving DLC?efficiency: How much of the capability is wasted by unnecess

5、ary waiting and by sending unnecessary retransmissions. 7ARQ (Automatic Repeat ReQuest)Three common schemesStop & WaitGo Back NSelective Repeat8An Example of Stop and WaitPacket 0 repeated because node A times-outNode A delays repeating packet 1 on the 2nd request for itAvoid unnecessary retransmiss

6、ion 9Stop and Wait (Sender) (with initial condition SN=0) Accept packet from higher layer when available; assign number SN to it 2) Transmit packet SN in frame with sequence # SN 3) Wait for an error free frame from B i. if received and it contains RNSN in the request # field, set SN to RN and go to

7、 1 ii. if not received within given time, go to 2 10Stop and Wait (Receiver)(with initial condition RN=0) Whenever an error-free frame is received from A with a sequence # equal to RN, release received packet to higher layer and increment RN.At arbitrary times, but within bounded delay after receivi

8、ng any error free frame from A, transmit a frame to A containing RN in the request # field. 11Go Back N ARQStop and Wait is inefficient when propagation delay is larger than the packet transmission timeCan only send packet per round-trip timeGo Back N ARQ is the most widely used type of ARQ protocol

9、Go Back N ARQ allows the transmission of new packets before earlier ones are acknowledgedGo Back N uses a window mechanism where the sender can send packets that are within a “window” of packetsThe window advances as acknowledgements for earlier packets are received 12Example of Go Back 7 ARQ 13Note

10、 that packet RN-1 must be accepted at B before a frame containing request RN can start transmission at B Selective Repeat Protocol (SRP) Selective Repeat attempts to retransmit only those packet actually lost (due to errors)Receiver must be able to accept packets out of orderSince receiver must rele

11、ase packets to higher layer in order, the receiver must be able to buffer some packetsRetransmission requestsImplicitThe receiver acknowledges every good packet, packets that are not ACKed before a time-out are assumed lost or in errorNotice that this approach must be used to be sure that every pack

12、et is eventually receivedExplicitAn explicit NAK can request retransmission of just one packetThis approach can expedite the retransmission but is not strictly neededOne or both approaches are used in practice 14ProblemsProblemsProblemsCH3 Delay Models in Data NetworksMultiplexing of traffic (1/2) M

13、ultiplexing of traffic(2/2) Random arrival in terms of依据；按照；在方面；以措词in accordance, in the light of, by, in the field ofnomenclature 英n()meklt;美nmnkltn. 命名法；术语M/M/mProblemsProblemsProblemsProblemsCh5: Routing in Data Networks10/1/202233Route a packet from a source to all nodes in the network Possible

14、solutions: Flooding: Each node sends packet on all outgoing links. How to limit the number of packet transmission? Discard packets received a second time, how? 5.1.2 Broadcast Routing10/1/20225.1.2 Broadcast RoutingPossible solutions: Spanning Tree Routing: Send packet along a tree that includes all

15、 of the nodes in the network.A spanning tree is a connected subgraph of the network that includes all nodes and has no cycles.Broadcasting on a spanning tree is more communication-efficient than flooding. The price of this saving is the need to maintain and update the spanning tree in the face of to

16、pological changes. 10/1/2022355.2 Spanning treesT = (N,A) is a spanning tree of G = (N,A) if T is a subgraph of G with N = N and T is a tree10/1/2022365.2 Spanning treesSpanning trees are useful for disseminating and collecting control information in networks; they are sometimes useful for routing T

17、o disseminate data from Node n: Node n broadcasts data on all adjacent tree arcs Other nodes relay data on other adjacent tree arcs To collect data at node n: All leaves of tree (other than n) send data Other nodes (other than n) wait to receive data on all but one adjacent arc, and then send receiv

18、ed plus local data on remaining arc 10/1/202237Min weight spanning tree(MST)Given a graph with weights assigned to each arc, find a spanning tree of minimum total weight (MST) Define a fragment“ to be a subtree of a MST Theorem: Given a fragment F of an MST, Let a(i,j) be a minimum weight out going

19、arc from F, where j is not in F. Then, F extended by arc a (i,j)& node j is a fragment. Proof: Let M be the MST that does not include a(i,j). Since a(i,j) is not part of M, then adding a (i,j) to M must cause a cycle. There must be some link in the cycle b a which is outgoing from F. Deleting b and

20、adding a creates a new spanning tree. Since weight of b cannot be less then weight of a , M must be a MST. If weight of a = weight of b, then both are MSTs otherwise M could not have been an MST 10/1/202238MST algorithmsGeneric MST algorithm steps: Given a collection of subtrees of an MST (called fr

21、agments) add a minimum weight outgoing edge to some fragment Prim-Dijkstra: Start with an arbitrary single node as a fragment Add minimum weight outgoing edge Kruskal: Start with each node as a fragment; Add the minimum weight outgoing edge, minimized over all fragments10/1/202239Shortest path algor

22、ithmsBellman-Ford algorithmFirst find the shortest single arc path, Then the shortest path of at most two arcs, etc.Let dij= if (i,j) is not an arc. Dijkstras algorithmThe Floyd-Warshall algorithmConsider a shortest path p from i to j such that the intermediate vertices are from the set 1,k. If the

23、vertex k is not an intermediate vertex on p, then dij(k) = dij(k-1)If the vertex k is an intermediate vertex on p, then dij(k) = dik(k-1) + dkj(k-1)Therefore, dij(k) = mindij(k-1) , dik(k-1) + dkj(k-1)Example using the Bellman-Ford and Dijkstra algorithmUsing the Bellman-Ford 10/1/202241Example usin

24、g the Bellman-Ford and Dijkstra algorithmUsing the Dijkstra10/1/202242The floyd-warshall algorithm- ExampleConsider Vertex 3: Nothing changes.Consider Vertex 2: D(1,3) = D(1,2) + D(2,3)Consider Vertex 1: D(3,2) = D(3,1) + D(1,2)Original weights.Network reliability issuesReliability requirementThe ne

25、twork is k-connected.K-connectedK-connected between two nodesTwo nodes are connected by deleting (k-1) nodesA graph is k-connected if every pair of nodes are k-connected. 10/1/202244Network reliability issuesCheck k-connectivityCheck each pair of nodes is too slowMore efficient method is expectedKle

26、itman method1) Choose an arbitrary node and check it k-connectivity to others2) Delete the checked node and its arcs, and check another nodes (k-1)-connectivity3) Continue untilthe last second node is checked to be 1-connected, orStop at some (k-i)-connectivity of some node10/1/202245ProblemsProblem

27、sProblemsproblemsProblemsMultiple AccessMultiple Access Shared Transmission Mediuma receiver can hear multiple transmitters a transmitter can be heard by multiple receivers the major problem with multi-access is allocating the channel between the users; the nodes do not know when the other nodes hav

28、e data to send Need to coordinate transmissions Approaches to Multiple AccessFixed Assignment (TDMA, FDMA, CDMA) each node is allocated a fixed fraction of bandwidthEquivalent to circuit switching very inefficient for low duty factor traffic Contention systems Polling Reservations and Scheduling Ran

29、dom Access There are n backlogged nodes, and m-n other nodesBacklogged node transmit a packet with probability qrThe rest nodes transmit in Poisson distribution with mean /mThe probability of no arrivals is e- /m. Then the probability with a packet arriving is qa=1- e- /mQa(i,n) : the probability th

30、at i unbacklogged nodes transmit packetsQr(i,n): the probability that i backlogged nodes transmit packetsThenMarkov chain for slotted aloha Throughput of Slotted AlohaThe throughput is the fraction of slots that contain a successful transmission = P(success) = g(n)e-g(n)When system is stable through

31、put must also equal the external arrival rate () Throughput of UnslottedAlohaAn attempt is successful if the inter-attempt intervals on both sides exceed 1 (for unit duration packets)P(success) = e-g(n) e-g(n) = e-2g(n) Throughput (success rate) = g(n)e-2g(n) For max throughput at g(n) = 1/2, Throug

32、hput = 1/2e 0.18stabilization issues are similar to slotted alohaadvantages of unslotted aloha are simplicity and possibility of unequal length packets Throughput comparisonstabilized pure aloha T = 0.184 = (1/(2e)stabilized slotted aloha T = 0.368 = (1/e)Carrier Sense Multiple Access (CSMA)In certa

33、in situations nodes can hear each other by listening to the channelIf the channel is sensed as busy, no node will attempt to use it until it goes idleThis is the basic idea of the Carrier Sense Multiple Access (CSMA) protocol.Analysis of CSMALet the state of the system be the number of backlogged node