Unformatted text preview:

1Prof. Adam WoliszTUBerlin/Vsiting Scholar UCBEE 225C Spring 2003 (Wireless) Networksare more than communications...☺Part IIEE 225C Spring 2003 2of 66Adam WoliszIntro ...• Who: Adam Wolisz– Professor of EE&CS at the Technische Universität Berlin (TUB) Germany– Chair of Telecommunication Networks, see www-tkn.ee.tu-berlin.de.– Visiting scholar at UCB : Berkeley Wireless Research CenterE-mail: [email protected]– Office hours: Just drop me a mail...☺• What: 3 lectures– Some basic protocol mechanisms, introduction to packet switched networks architecture– Multiple Access Control : Basics, Random Access mechanisms– MAC in IEEE 802.11EE 225C Spring 2003 3of 66Adam WoliszOverview - Multiple Access• Introduction• Time Division Multiple Access – TDMA• Polling-based Approach• ALOHA/Slotted ALOHA• Stability, exponential backof• Carrier Sense Multiple Access – CSMA; variants.• PRMA, MACA/MACAW ...Usage of slides from .Jochen Schiller, Shamim Begum, Hammond& O´Reilly is acknowledged!EE 225C Spring 2003 4of 66Adam WoliszMultiple Access - Introduction• Problem: We have several DISTRIBUTED stations sharing a medium. Only ONE can send in a given time interval.• How to arrange the sharing of the medium? • Note the similarity and the difference to the multiplexing discussed previously.• Both centralized and - preferably! - distributed schemata are considered.• A fundamental problem for any shared medium!!Note: A book by Raphael Rom and Moshe Sidi „Multiple Access Protocols“, Springer Verlag 1990 is available on-line under www-comnet.technion.ac.il/rom/PDF/MAP.pdfEE 225C Spring 2003 5of 66Adam WoliszTime-Division Multiple Access (1)EE 225C Spring 2003 6of 66Adam WoliszTime-Division Multiple Access (2)EE 225C Spring 2003 7of 66Adam WoliszTime-Division Multiple Access (3)EE 225C Spring 2003 8of 66Adam WoliszPollingEE 225C Spring 2003 9of 66Adam WoliszPolling: Message FlowEE 225C Spring 2003 10 of 66Adam WoliszPolling: action descriptionEE 225C Spring 2003 11 of 66Adam WoliszPolling: Queue dynamics...EE 225C Spring 2003 12 of 66Adam WoliszPolling-based Approach: Features• Central station needed (Migh be elected in dynamic way)...• Several parameter might be influenced– The number of included stations– Exhaustive or non-exhaustive service of individual stations.– Sequence of polling - might be application specific, like– 123145167189123• Under certain assumptions the upper limit on delay could be assured...• Easy to organize...BUT :essential problem: joining the virtual ring (contention unavoidable): WHO DOES BELONG??EE 225C Spring 2003 13 of 66Adam WoliszPolling-based Approach: Participation• Just an example (Kings College)– An “Open Request” is issued without polled_station_id– Each competing station• sends a Request-To-Join (RTJ) with own un_id x• waits for being polled explicitly• after a timeout (RTJ collided?)• Repeat the attempt after a stochastic backoff measured in numbers of “Open Requests”•Obviously not a good idea in case of high dynamic of the number of stations...EE 225C Spring 2003 14 of 66Adam WoliszToken bus...like IEEE 802.4• Take a set of stations, order them in a „Virtual ring“ by setting a sequence in which this stations are to be served...• Only the station posessing a token is allowed to transmit, for some limited time...• After expiration of this time, token has to be passed to the „Follower“ in the virtual ring....• A neatly distributed approach... But– How to configure the virtual ring?– Graceful leaving of the ring: Giving the followers address to the predecessor– Ungraceful leaving• Operation on wireless channels bad: Loosing the membershipEE 225C Spring 2003 15 of 66Adam WoliszRandom Access Approach• Invented by Abramson for radio communication between several end-systems and a single central station (Havaii Islands). The number of station has been high, traffic from each station low, and not predictable.....• One frequency used for the uplink (end-system to base station). another for the downlink• A beautiful idea: Just talk whenever you like... Can this work at all? Yes.... See small children....• Sure, packets can collide,....but only in the uplink. On the downlink there are no collisions, as the single base station sends information one-by-one...• The base station is requested to acknowledge each packet, so the sender knows if his last attempt has been successful.• Stochastic delay before re-trial. Why?EE 225C Spring 2003 16 of 66Adam WoliszALOHA /slotted ALOHA - Block DiagramEE 225C Spring 2003 17 of 66Adam WoliszList of Parameters• τ Propagation delay [s]• X Message length [byte]• R Transmission speed [bit/s]• P=8X/R Packet duration [s]• a=τ/P normalized propagation delay• T average transfer delay • T normalized transfer delay (in packet duration)• S Throughput: number of packets effectively transmittedduring a packet duration• G Number of packets offered for transmission (incl. repetition) during a packet duration• M Number of sources• J Duration of jam• γ=J/τEE 225C Spring 2003 18 of 66Adam WoliszALOHA (3)EE 225C Spring 2003 19 of 66Adam WoliszALOHA (3)• Consider the offered traffic as having POISSON distribution with rate ΛΛΛΛ(which is NOT exactly true...)• Probability of k arrivals in t seconds isAssuming start of the target packet at t0each packet arriving in the period [ t0-P][ t0+P] will cause a collision....PR k in[t][]=(Λt)kk!e−ΛτPR 0 arrivals[]= e−ΛtPR 0 arrivals per(2P seconds)[]= e−2GS= Ge−2GEE 225C Spring 2003 20 of 66Adam WoliszStability of ALOHA (1)• For a finite population of M users with an average of n station backlogged and waiting, (M-n) stations can generate new packets. Let the probability of one free station generating a packet be denoted σ. It then follows that the total input packet rate, S, from the (M-n) free stations is given by:S= (M-n) σ• With M and σconstant defines a straight line as the load line in the (n,S) plane.• The intersection of the throughput-backlog curve and the load line are the points that specify possible operating values of throughput.• Consider four cases of channel operations– a) Stable– b) Unstable but locally bistable– c) Stable but overloaded– d) Unstable (this is btw. The case of infinitely many stations...)EE 225C Spring 2003 21 of 66Adam


View Full Document

Berkeley ELENG 225C - Lecture Notes

Download Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?