From crose Tue Sep 9 09:58:17 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA02112; Tue, 9 Sep 97 09:58:16 EDT Date: Tue, 9 Sep 97 09:58:16 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709091358.AA02112@MOGLI.rutgers.edu> To: 330_543 Subject: problem set 1 Status: RO Problem set 1 is available on the web. It is due 9/16/97 if you'd like the TA to look at it. No late submissions allowed. Cheers, Chris Rose From crose Thu Sep 11 21:17:16 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA02680; Thu, 11 Sep 97 21:17:15 EDT Date: Thu, 11 Sep 97 21:17:15 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709120117.AA02680@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: mailing list Status: RO Hi Folks, This is the latest test of the mailing list! 1) 501 FOLK: Good class (for me... had fun). I"m going to have to do less proving and more lecturing... but I know I won't :) In any case, read up through the linear algebra stuff on matrix norms and onward to functions of matrices I'd like to get through chapter 1 by (AT THE LATEST) the end of next week. It's tough going, but it's useful as a thinking organizer 2) 543 FOLK: At Zhou Lin's suggestion I'm going to go over the TDM switch example (framining and "diagonal" discovery) again next class just ot make sure it stuck. Start reading chapter 3. I think we'll fly through it since most of the proofs are reasonably easy. Cheers, Chris Rose From crose@localhost.localdomain Mon Sep 15 22:02:09 1997 Return-Path: Received: from localhost.localdomain (ppp-13.ts-7.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA07497; Mon, 15 Sep 97 22:02:01 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id VAA29311 for 330_543@mogli.rutgers.edu; Mon, 15 Sep 1997 21:00:25 -0400 Date: Mon, 15 Sep 1997 21:00:25 -0400 From: Christopher Rose Message-Id: <199709160100.VAA29311@localhost.localdomain> To: 330_543@mogli.rutgers.edu Subject: problem set 2 Status: RO Problem set 2 consists of Chapter 3: P1,P2,P5 & P8 Chapter 4: P1, P2, & P4 It is due on 9/23/97. Cheers Chris Rose From crose Tue Sep 16 16:18:32 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA08594; Tue, 16 Sep 97 16:18:31 EDT Date: Tue, 16 Sep 97 16:18:31 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709162018.AA08594@MOGLI.rutgers.edu> To: minfan@paul.rutgers.edu Subject: Re: Office hour for the TA Cc: 330_501, 330_543 Status: RO ************* Could you please tell me what is the office hour for the TA? I have lots of questions which I can figure out my self. Thanks. ********************* Hi, Have you tried posting your questions to the mailing list yet? That's the first thing to do. Also, to which course do you refer (501 or 543). Cheers, Chris Rose From crose Tue Sep 16 16:28:23 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA08641; Tue, 16 Sep 97 16:28:23 EDT Date: Tue, 16 Sep 97 16:28:23 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709162028.AA08641@MOGLI.rutgers.edu> To: 330_543 Subject: test Cc: crose@MOGLI.rutgers.edu Status: RO REMINDER: Test on Thursday 9/25 in class and period afterward as well NO CLASS Tuesday 9/30 CHeers, Chris Rose From minfan@paul.rutgers.edu Tue Sep 16 16:35:29 1997 Return-Path: Received: from paul.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA08661; Tue, 16 Sep 97 16:35:28 EDT Received: from localhost (minfan@localhost) by paul.rutgers.edu (8.8.5/8.8.5) with SMTP id PAA14395 for ; Tue, 16 Sep 1997 15:42:53 -0400 (EDT) Date: Tue, 16 Sep 1997 15:42:52 -0400 (EDT) From: Min Fan To: Christopher Rose Subject: Re: Office hour for the TA In-Reply-To: <9709162018.AA08594@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO > Hi, > > Have you tried posting your questions to the mailing list yet? > That's the first thing to do. Also, to which course do you refer > (501 or 543). I am attending 543. I think we have a FULL time TA, so at least FULL time TA should have office hour. I am in CS major. It looks I could not understand some of the assumption in the book. So that I have LOTS of questions. I think an interatvie discussion in person will help me. I look at your solutions for hw1. I still do not understand question 4 of chapter 2. So I do not think discuss it on line is a good way. Thanks. Min Fan > > Cheers, > > Chris Rose > From crose Tue Sep 16 16:43:29 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA08692; Tue, 16 Sep 97 16:43:28 EDT Date: Tue, 16 Sep 97 16:43:28 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709162043.AA08692@MOGLI.rutgers.edu> To: minfan@paul.rutgers.edu Subject: Re: Office hour for the TA Cc: 330_543 Status: RO thanks. I'll post the TA's office hours as soon as they are available. The TA by the way is Wenfeng Zhang and his email address is zwf@winlab.rutgers.edu so you can contact him directly. Cheers, CHris Rose From chriskly@er3.rutgers.edu Wed Sep 17 10:35:04 1997 Return-Path: Received: from er3.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA09625; Wed, 17 Sep 97 10:35:04 EDT Received: (from chriskly@localhost) by er3.rutgers.edu (8.8.5/8.8.5) id JAA00348; Wed, 17 Sep 1997 09:42:19 -0400 (EDT) Date: Wed, 17 Sep 97 9:42:19 EDT From: Christine Kleiwerda To: 330_543@mogli.rutgers.edu Cc: crose@mogli.rutgers.edu Subject: end of last class... Message-Id: Status: RO Professor Rose and anyone else who can answer- Thinking about the rules we went over at the end of class yesterday, wouldnt it be more exact to say that the max # of distinct entries per row is min(m1,r2)? Consider the case where m1=5 and r2=2. Then the max # entries is 2, not 5. Right? Or what am I missing? Christine From jpapa@mail.monmouth.com Wed Sep 17 12:06:10 1997 Return-Path: Received: from shell.monmouth.com by MOGLI.rutgers.edu (4.1/25-eef) id AA09733; Wed, 17 Sep 97 12:06:09 EDT Received: from rb-tc-ppp17.monmouth.com (rb-tc-ppp17.monmouth.com [208.7.184.101]) by shell.monmouth.com (8.8.5/8.7.3) with SMTP id LAA20120; Wed, 17 Sep 1997 11:10:05 -0400 (EDT) Received: by rb-tc-ppp17.monmouth.com with Microsoft Mail id <01BCC35A.5BDFD540@rb-tc-ppp17.monmouth.com>; Wed, 17 Sep 1997 11:10:51 -0400 Message-Id: <01BCC35A.5BDFD540@rb-tc-ppp17.monmouth.com> From: Joseph Papa To: "'Christine Kleiwerda'" Cc: "'330_543@mogli.rutgers.edu'" <330_543@mogli.rutgers.edu> Subject: RE: end of last class... Date: Wed, 17 Sep 1997 11:10:40 -0400 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Status: RO Yeah, you're exactly right (see Figure 6 in Chp.3). I think what Prof. = Rose was trying to say is that in practice r2 is usually greater than m1 = or n3, so the limiting factor is usually not r2 (IN PRACTICE).=20 Joe -----Original Message----- From: Christine Kleiwerda [SMTP:chriskly@eden.rutgers.edu] Sent: Wednesday, September 17, 1997 9:42 AM To: 330_543@MOGLI.rutgers.edu Cc: crose@MOGLI.rutgers.edu Subject: end of last class... Professor Rose and anyone else who can answer- Thinking about the rules we went over at the end of class yesterday, = wouldnt it be more exact to say that the max # of distinct entries per row is min(m1,r2)? =20 Consider the case where m1=3D5 and r2=3D2. Then the max # entries is 2, = not 5.=20 Right? Or what am I missing?=20 Christine From crose Wed Sep 17 13:00:57 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA09782; Wed, 17 Sep 97 13:00:56 EDT Date: Wed, 17 Sep 97 13:00:56 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709171700.AA09782@MOGLI.rutgers.edu> To: 330_543@mogli.rutgers.edu, chriskly@eden.rutgers.edu Subject: Re: end of last class... Cc: crose Status: RO Yup! That would be the completely accurate statement and completely general (for clos point-2-point networks). The basic assumption in Joe's book however is that n1 >= m1 since the switch will be a blocking switch otherwise. Other comments welcome. Keep writing! CHeers, Chris Rose From elf_pub@email.rutgers.edu Wed Sep 17 23:01:50 1997 Return-Path: Received: from eden-backend.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA10870; Wed, 17 Sep 97 23:01:49 EDT Received: from chef24.rutgers.edu (chef24.rutgers.edu [165.230.129.153]) by eden-backend.rutgers.edu (8.8.5/8.8.5) with SMTP id WAA16101 for <330_543@mogli.rutgers.edu>; Wed, 17 Sep 1997 22:09:02 -0400 (EDT) Message-Id: <34208A7F.41B0@email.rutgers.edu> Date: Wed, 17 Sep 1997 21:57:19 -0400 From: Public ELF Workstation Reply-To: "no reply"@eden.rutgers.edu Organization: Rutgers University Libraries X-Mailer: Mozilla 3.01 (Win16; I) Mime-Version: 1.0 To: 330_543@mogli.rutgers.edu Subject: distinct symbols Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO Hi, At the end of last class, we was told that each raw of Paull's Matrix From vpopescu@caip.rutgers.edu Thu Sep 18 01:50:48 1997 Return-Path: Received: from caipfs.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA11072; Thu, 18 Sep 97 01:50:47 EDT Received: from tekka.rutgers.edu (tekka.rutgers.edu [128.6.43.14]) by caipfs.rutgers.edu (8.8.5/8.8.5) with ESMTP id AAA12145; Thu, 18 Sep 1997 00:57:45 -0400 (EDT) From: Viorel George Popescu Received: (vpopescu@localhost) by tekka.rutgers.edu (8.7.6/8.6.9) id AAA10333; Thu, 18 Sep 1997 00:57:44 -0400 (EDT) Date: Thu, 18 Sep 1997 00:57:44 -0400 (EDT) Message-Id: <199709180457.AAA10333@tekka.rutgers.edu> To: 330_543@mogli.rutgers.edu Cc: vpopescu@caip.rutgers.edu Status: RO They don't have to be distinct. Eg. assume m1=r2=n3; then you anyway don't have more than r2 symbols (second stage switches). Therefore they (collections of different symbols on row and collection of different symbols on column) overlap. But they don't have to be identical. If r2>m1 or r2>n3 then these collections have at least max(0, (min(m1,r2)+min(n3,r2)-r2) ) common symbols (you can find examples). My understanding of the problem is the following: 1. You get the maximum # of different symbols in a row if you consider the entire flow (traffic) going through only one switch in the first stage if r2>m1. The flow has to span to different second stage switches (no path overlaping). If r2m1=n3, by choosing to route the traffic through a single input switch and a single third stage switch; then you squeeze all symbols (m1=n3) in one element of the matrix. This is just an example. You cannot do that all the time because you have to solve conflicts in the switch (using input stage) and rearange the pachet order (third switch). For a non-blocking Clos network the proof of theorem (pp. 65) uses somehow the fact that you should have different symbols on row and columns, but I didn't get the meaning of that. My understanding of non-blocking for Clos network is as follows: you establish m1-1 connections (assume r2>m1, r2>n3) and you are trying to fit the last one. You want to be able to fit it anywhere: from any input to any output. To not disturb the already existent paths, you need n3 additional second stage switches, so that you can place any input in any output slot. If previous statements are not true, please send corrections and comments. Cheers, George > Hi , > > At the end of the class, we were told that each row of Paull's Matrix > can have at most m1 distinct symbols. Each columm can have at most n3 > distinct symbols. Here symbols are different from each other within a > row or a column. For instance, row a and column b may have m1+n3 > symbols, do they have to distinct each other? It depends on blocking of > the network? > if it is a nonblocking network? > > I will appreciate if some one gives the answer. Otherwise, it will be > covered next class. > From crose Thu Sep 18 02:21:55 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA11104; Thu, 18 Sep 97 02:21:54 EDT Date: Thu, 18 Sep 97 02:21:54 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709180621.AA11104@MOGLI.rutgers.edu> To: 330_543@mogli.rutgers.edu, vpopescu@caip.rutgers.edu Subject: Paull's Matrix Status: RO Hi FOlks, The issue is one of point-2-point switching. If it's not point to point, then the distinctness constraint is gone. However, if you have point to point then each row can have a max of m1 symbols (all distinct... think about it... there are only m1 different switches you can get to at one time from a given input switch bank... you have to choose from r2>= m1 possible symbols, but you can only have m1 before you've used the switch up). Same argument for the columns (only now the limit it n3). By the way, a side issue which is kind of swept under the rug is that we do not consider networks which are blocking. We're only looking at rearrangeable networks and strict sense non-blocking networks. This is the reason that n1 >= m1 and m3 >= n3. Such networks are blocking --- can't have all inputs on a given input switch bank active at once (same for output switch banks) no matter what (can't sneak around the problem by rearrangement). Cheers, Chris Rose From crose Thu Sep 18 02:24:35 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA11115; Thu, 18 Sep 97 02:24:35 EDT Date: Thu, 18 Sep 97 02:24:35 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709180624.AA11115@MOGLI.rutgers.edu> To: 330_543 Subject: erratum Status: RO On my last mail message I said in the last sentence that such networks are blocking... what I meant was taht netorks with n1 < m1 and m3 < n3 are blocking. Sorry 'bout that.. From crose Thu Sep 18 02:26:37 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA11126; Thu, 18 Sep 97 02:26:37 EDT Date: Thu, 18 Sep 97 02:26:37 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709180626.AA11126@MOGLI.rutgers.edu> To: 330_543 Subject: by the way Status: RO Hey Folks, There is an archive of all email snt by the class on this address (330_543) linked to the web page. It's in text form (just a copy of my save file for class correspondence). Cheers (again) From chriskly@er3.rutgers.edu Wed Sep 17 10:35:04 1997 Return-Path: Received: from er3.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA09625; Wed, 17 Sep 97 10:35:04 EDT Received: (from chriskly@localhost) by er3.rutgers.edu (8.8.5/8.8.5) id JAA00348; Wed, 17 Sep 1997 09:42:19 -0400 (EDT) Date: Wed, 17 Sep 97 9:42:19 EDT From: Christine Kleiwerda To: 330_543@mogli.rutgers.edu Cc: crose@mogli.rutgers.edu Subject: end of last class... Message-Id: Status: RO Professor Rose and anyone else who can answer- Thinking about the rules we went over at the end of class yesterday, wouldnt it be more exact to say that the max # of distinct entries per row is min(m1,r2)? Consider the case where m1=5 and r2=2. Then the max # entries is 2, not 5. Right? Or what am I missing? Christine From jpapa@mail.monmouth.com Wed Sep 17 12:06:10 1997 Return-Path: Received: from shell.monmouth.com by MOGLI.rutgers.edu (4.1/25-eef) id AA09733; Wed, 17 Sep 97 12:06:09 EDT Received: from rb-tc-ppp17.monmouth.com (rb-tc-ppp17.monmouth.com [208.7.184.101]) by shell.monmouth.com (8.8.5/8.7.3) with SMTP id LAA20120; Wed, 17 Sep 1997 11:10:05 -0400 (EDT) Received: by rb-tc-ppp17.monmouth.com with Microsoft Mail id <01BCC35A.5BDFD540@rb-tc-ppp17.monmouth.com>; Wed, 17 Sep 1997 11:10:51 -0400 Message-Id: <01BCC35A.5BDFD540@rb-tc-ppp17.monmouth.com> From: Joseph Papa To: "'Christine Kleiwerda'" Cc: "'330_543@mogli.rutgers.edu'" <330_543@mogli.rutgers.edu> Subject: RE: end of last class... Date: Wed, 17 Sep 1997 11:10:40 -0400 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Status: RO Yeah, you're exactly right (see Figure 6 in Chp.3). I think what Prof. = Rose was trying to say is that in practice r2 is usually greater than m1 = or n3, so the limiting factor is usually not r2 (IN PRACTICE).=20 Joe -----Original Message----- From: Christine Kleiwerda [SMTP:chriskly@eden.rutgers.edu] Sent: Wednesday, September 17, 1997 9:42 AM To: 330_543@MOGLI.rutgers.edu Cc: crose@MOGLI.rutgers.edu Subject: end of last class... Professor Rose and anyone else who can answer- Thinking about the rules we went over at the end of class yesterday, = wouldnt it be more exact to say that the max # of distinct entries per row is min(m1,r2)? =20 Consider the case where m1=3D5 and r2=3D2. Then the max # entries is 2, = not 5.=20 Right? Or what am I missing?=20 Christine From crose Thu Sep 18 11:17:39 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA11785; Thu, 18 Sep 97 11:17:38 EDT Date: Thu, 18 Sep 97 11:17:38 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709181517.AA11785@MOGLI.rutgers.edu> To: 330_543@mogli.rutgers.edu, chriskly@eden.rutgers.edu Subject: Re: end of last class... Cc: crose@mogli.rutgers.edu Status: RO Hi Christine, The issue (I think this has come up in a few emails before) is that if r2=2 and m1=5, the switch is automatically blocking... you can never use all m1 inputs at the same time. So m1 is always assumed to be less than or equal to r2. A similar argument applies to r2 and n3. Hope that helps.... Cheers Chris Rose From crose Thu Sep 18 11:19:23 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA11791; Thu, 18 Sep 97 11:19:22 EDT Date: Thu, 18 Sep 97 11:19:22 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709181519.AA11791@MOGLI.rutgers.edu> To: 330_543@mogli.rutgers.edu, chriskly@eden.rutgers.edu Subject: Re: end of last class... Cc: crose@mogli.rutgers.eduret Status: RO Ignore my last mail since it was a rehash of a previously asked and answered question. (I had an open mail tool which I did not delete from yesterday). Cheers, Chris Rose From nirajp@er5.rutgers.edu Fri Sep 19 11:13:42 1997 Return-Path: Received: from eden-backend.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA00206; Fri, 19 Sep 97 11:10:36 EDT Received: from er5.rutgers.edu (nirajp@er5.rutgers.edu [165.230.180.133]) by eden-backend.rutgers.edu (8.8.5/8.8.5) with ESMTP id AAA05676 for <330_543@MOGLI.rutgers.edu>; Fri, 19 Sep 1997 00:12:43 -0400 (EDT) Received: from localhost (nirajp@localhost) by er5.rutgers.edu (8.8.5/8.8.5) with SMTP id AAA10453 for <330_543@MOGLI.rutgers.edu>; Fri, 19 Sep 1997 00:09:24 -0400 (EDT) Date: Fri, 19 Sep 1997 00:09:23 -0400 (EDT) From: Niraj Prabhavalkar To: 330_543@MOGLI.rutgers.edu Subject: vci Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO hi, i'm not very sure about the vci concept yet but this is what i think. its called virtual because it changes from time to time and is not dependent on the physical link but on the number of active users at a time. so the address changes accordingly. another thing is about todays class. i was slightly lost. can someone tell me about the second and third theorems please. waiting for a reply niraj. From crose Fri Sep 19 12:59:43 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00370; Fri, 19 Sep 97 12:59:42 EDT Date: Fri, 19 Sep 97 12:59:42 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709191659.AA00370@MOGLI.rutgers.edu> To: nirajp@eden.rutgers.edu Subject: Re: vci Cc: crose@MOGLI.rutgers.edu Status: RO Hi, I'll take a crack at your questions first: 1) A VIRTUAL ckt as opposed to a real circuit is a concept related to packetization of information. In the old days, a real circuit implied a real wire and a real hunk of bandwidth on various links that was used ALL THE TIME by the call in progress. And since we were usually talking TDM or FDM (frequency/time division multiplexing) that implied particular frequencies and times were assigned to carry a call on each leg of it's journey. In a VIRTUAL setting there are no explicit revervations of time slots and channels. There is just a guarantee of availability. SO, that means each packet has to have an identifier which states that it has a reservation for resources AND THIS MUST BE DONE FOR EACH LEG OF THE PACKET's TRIP! Thus, you have a VIRTUAL circuit IDENTIFIER for each packet and at each leg, you might have different ID numbers for the same conversation (VCI translation tables). 2) Not sure how to help here. What I'd suggest is follow the logic through (why must m1 < n1, and similarly for the output swtiches) and then play devil's advocate and find worst case scenarios for when you can't find paths without rearangement. For the rearrangment, draw another picture corresponding to the case where you need to do one rearrangment so you get a physical feel for what's happening. Then do two... I think the rearrangement proof will become clear at that point. For the double chain argument for maximum numbers of rearrangments, that's just a counting proof which is clear if you understand the rearrangeability proof I think. Hope that helps, but everyone chime in please as well! Cheers, Chris Rose From chriskly@er5.rutgers.edu Fri Sep 19 15:57:55 1997 Return-Path: Received: from er5.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA00729; Fri, 19 Sep 97 15:57:55 EDT Received: (from chriskly@localhost) by er5.rutgers.edu (8.8.5/8.8.5) id PAA22250; Fri, 19 Sep 1997 15:04:49 -0400 (EDT) Date: Fri, 19 Sep 97 15:04:49 EDT From: Christine Kleiwerda To: Niraj Prabhavalkar Cc: 330_543@MOGLI.rutgers.edu Subject: Re: vci In-Reply-To: Your message of Fri, 19 Sep 1997 00:09:23 -0400 (EDT) Message-Id: Status: RO > hi, > i'm not very sure about the vci concept yet but this is what i think. > its called virtual because it changes from time to time and is not > dependent on the physical link but on the number of active users at a > time. so the address changes accordingly. > another thing is about todays class. i was slightly lost. > can someone tell me about the second and third theorems please. > waiting for a reply > niraj. > > > i'm not sure which ones you are callining the 2nd and 3rd theorems, but i think you mean the rearrangable non blockign ones (RNB) ... 1. a 3 stage clos net is RNB if r2 > max (m1, n3). To me, this means that the number of middle switches must be greater than both the number of inputs and the number of outputs. Otherwise, say the number of middle switches is less than teh number of inputs, then it is possible that all the middle switches are being used when a new input is looking for a connection. Then this newest input is blocked (ther is no possible way for a connection to be made). Same argument for the output side. 2. an upper bound on the max # of rearrangements is min (r1,r3) - 1 Using Paull's matrix, each time you do a rearrangement, you are eliminating one row and one col from the "pool" where you can make the rearrangments. (I'm notquite sure what this translates to in the switch terminology... i think it's something like each time you do a rearrangement, you are changing which switch a path goes through and you can only make this rearrangement once??) Anyway, back to Paull's matrix.. .you can keep making rearrangements until you run out of rows or cols , whichever comes first. There are r1 rows and r3 cols total in the matrix. When you start, you immediately eliminate the row and col you are trying to connect, so you are left with r1-1 possible rows and r3-1 possible cols. The max # of rearrangements is the min of these, min(r1-1, r3-1) = min (r1, r3) - 1. Does this make sense? Is this what you were looking for? Christine From chriskly@er6.rutgers.edu Fri Sep 19 22:21:32 1997 Return-Path: Received: from er6.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA01348; Fri, 19 Sep 97 22:21:29 EDT Received: (from chriskly@localhost) by er6.rutgers.edu (8.8.5/8.8.5) id VAA03619; Fri, 19 Sep 1997 21:28:22 -0400 (EDT) Date: Fri, 19 Sep 97 21:28:21 EDT From: Christine Kleiwerda To: 330_543@mogli.rutgers.edu, linzhou@ece.rutgers.edu Subject: [Lin Zhou : Re: vci] Message-Id: Status: RO >From what I understood from class, here's the way to do it: We know there is at least one switch available to connect to a and another switch available to connect to b. Our problem is that these are not the same switches. Call a's free switch Sa and b's free switch Sb. Since Sa does not equal Sb, we know that there must be an entry in col b equal to Sa. We look in the row where Sa is for an entry of Sb. If Sb is not in that row, then we can change Sa to Sb and use Sa for the connection from a to b. If Sb is in that row, then we search the column where Sb is, looking for Sa. If there is no Sa, then we can change the Sb to Sa, and the Sa (from row b) to Sb and use Sa to complete the connection from a to b. And you can continue this process.... Basically, I think the concept is that we are going to use Sa to complete the connection. But, Sa is already used by b, so we need to replace that connection by Sb, which may already be used in that row, so we replace it with Sa, which may already be used in that col, so we replace it with Sb, which may already be used in that row, etc..... Eventually, we will reach a point where the switch we want to use is not already being used in that row/col and then we can go ahead and make all the rearrangements. Does this help at all? I'm trying to figure out why we are guaranteed "eventually, we will reach a point where the switch we want to use is not already being used in that row/col" and cant quite see the answer yet...... Anyone have an idea??? Somehow, it must be because we know Sa is available in row a and Sb is available in row b. Christine --------------- Received: from ece.rutgers.edu (ece.rutgers.edu [128.6.46.12]) by eden-backend.rutgers.edu (8.8.5/8.8.5) with SMTP id PAA02548 for ; Fri, 19 Sep 1997 15:44:01 -0400 (EDT) Received: from localhost (linzhou@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id PAA03785 for ; Fri, 19 Sep 1997 15:39:45 -0400 Date: Fri, 19 Sep 1997 15:39:45 -0400 (EDT) From: Lin Zhou To: Christine Kleiwerda Subject: Re: vci In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Hi Christine, The upbound of rearrangement nonblocking network is min(r1,r3)-1 with your explanation. How can you do the arrangement one by one after delete one row and one column? Though you can eat at most min(r1,r3) row or col finally, How is arrangement doing? The goal is to put a distinct entry to [a,b]. zhou lin From chriskly@er3.rutgers.edu Fri Sep 19 22:36:50 1997 Return-Path: Received: from er3.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA01424; Fri, 19 Sep 97 22:36:49 EDT Received: (from chriskly@localhost) by er3.rutgers.edu (8.8.5/8.8.5) id VAA04197; Fri, 19 Sep 1997 21:43:42 -0400 (EDT) Date: Fri, 19 Sep 97 21:43:42 EDT From: Christine Kleiwerda To: 330_543@mogli.rutgers.edu, crose@mogli.rutgers.edu Subject: exam Message-Id: Status: RO Professor Rose- Is the exam next thursday open book? What chapters will it cover? Christine From crose Fri Sep 19 22:45:50 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA01439; Fri, 19 Sep 97 22:45:49 EDT Date: Fri, 19 Sep 97 22:45:49 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709200245.AA01439@MOGLI.rutgers.edu> To: 330_543@mogli.rutgers.edu, chriskly@eden.rutgers.edu, crose@mogli.rutgers.edu Subject: Re: exam Cc: crose@MOGLI.rutgers.edu Status: RO Hi Christine, 1) thanks for the various explanations: you're eventually guaranteed to stop because you'll eventually run out of rows and columns to find stuff in! If you're lucky and run out of things to find before then, then you count your blessings. 2) The test is NOT open book. However, take a peek at the info sheet and you'll see that you can have a single 2-sided sheet of 8.5x11 note paper with handwritten notes on it. That should help both as a study aid and security blanket :) The test will be on chapters 1-3 and possibly part of chapter 4. Cheers (all) Chris Rose From aonweller@maerskdata-usa.com Sat Sep 20 14:16:17 1997 Return-Path: Received: from msrvr.maerskdata-usa.com by MOGLI.rutgers.edu (4.1/25-eef) id AA02068; Sat, 20 Sep 97 14:16:16 EDT Received: from [10.1.25.41] ([207.242.160.66]) by msrvr.maerskdata-usa.com (Netscape Mail Server v2.02) with SMTP id AAA96 for ; Sat, 20 Sep 1997 17:26:04 +0000 Message-Id: <34240673.4BA7@maerskdata-usa.com> Date: Sat, 20 Sep 1997 13:23:00 -0400 From: aonweller@maerskdata-usa.com (Allen Onweller) X-Mailer: Mozilla 3.01-C-MACOS8 (Macintosh; I; PPC) Mime-Version: 1.0 To: crose@mogli.rutgers.edu Subject: Web Site not accessable Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO Hi Prof. Rose. I seem to be having problems accessing any sites in the ece.rutgers.edu domain (I get a connection refused error.) I can get to the main Rutgers site (www.rutgers.edu) just fine though. The problem is that I haven't downloaded problem set two yet and I was planning on working on it today and Sunday. I was wondering if it wouldn't be too much trouble for you to e-mail the pproblem set to the e-mail list. (I'm assuming that there are others in need also.) Regards, Allen From crose Sat Sep 20 19:48:08 1997 To: cripop@ece.rutgers.edu Subject: Re: mailing list error Cc: s corresp/543 Status: O Glad to repost. The machines were down on thursday... Cheers, From cripop@ece.rutgers.edu Sat Sep 20 17:49:33 1997 Return-Path: Received: from zen.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA02185; Sat, 20 Sep 97 17:49:32 EDT Received: from chess.rutgers.edu (chess.rutgers.edu [128.6.46.113]) by zen.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id QAA02602 for ; Sat, 20 Sep 1997 16:52:18 -0400 From: Dimitrie Popescu Message-Id: <199709202052.QAA02602@zen.rutgers.edu> Subject: mailing list error To: crose@ece.rutgers.edu Date: Sat, 20 Sep 1997 16:46:48 -0400 (EDT) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 2992 Status: RO Dear dr. Rose, I have tried to send the following message to the 330_501 mailing list (330_501@mogli.rutgers.edu) but it has been returned twice with the same error message "User unknown". Did I do something wrong? Also, maybe you can post the following message to the mailing list. Otilia Popescu PS. I receive messages from 330_501@mogli.rutgers.edu, but I haven't been able to send any messages. >From Postmaster Fri Sep 19 12:43:15 1997 Received: from localhost (localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with internal id MAA10603; Fri, 19 Sep 1997 12:43:15 -0400 Date: Fri, 19 Sep 1997 12:43:15 -0400 From: Mail Delivery Subsystem Subject: Returned mail: User unknown Message-Id: <199709191643.MAA10603@ece.rutgers.edu> To: cripop MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="MAA10603.874687395/ece.rutgers.edu" Status: RO This is a MIME-encapsulated message --MAA10603.874687395/ece.rutgers.edu The original message was received at Fri, 19 Sep 1997 12:43:13 -0400 from cripop@localhost ----- The following addresses had delivery problems ----- 330_501@mogli.rutgers.edu (unrecoverable error) ----- Transcript of session follows ----- ... while talking to mogli.rutgers.edu.: >>> RCPT To:<330_501@mogli.rutgers.edu> <<< 550 /usr/crose/system/501: line 2: utgers.edu... User unknown 550 330_501@mogli.rutgers.edu... User unknown ----- Original message follows ----- --MAA10603.874687395/ece.rutgers.edu Content-Type: message/rfc822 Return-Path: cripop Received: (from cripop@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) id MAA10602 for 330_501@mogli.rutgers.edu; Fri, 19 Sep 1997 12:43:13 -0400 Date: Fri, 19 Sep 1997 12:43:13 -0400 From: Dimitrie Popescu Message-Id: <199709191643.MAA10602@ece.rutgers.edu> To: 330_501@mogli.rutgers.edu Subject: Cayley-Hamilton Theorem Content-Length: 1048 This is a proof of the Cayley-Hamilton Theorem in the general case. No assumption is made about matrix A; just that is a square matrix of dimension nxn. Let us denote the characteristic polynomial of A: Phi(s)=det(sI-A)=s^n+a_1s^(n-1)+...+a_n Let us also take the inverse of sI-A: (sI-A)^(-1)=(sI-A)*/det(sI-A)=B(s)/Phi(s) where (sI-A)*=B(s) is the adjoint matrix of sI-A. Rewrite the above relation as: Phi(s)I_n=(sI-A)B(s) because the highest power of s in Phi(s) is n, then the highest power of s in B(s) will be n-1. B(s) can be written as: B(s)=B_0s^(n-1)+B_1s(n-2)+...+B_(n-1) After performing the multiplication and identifying coefficients we get: s^n: I=B_0 s^(n-1): a_1I=B_1-AB_0 s^(n-2): a_2I=B_2-AB_1 ........ s^1: a_(n-1)I=B_(n-1)-AB_(n-2) s^0: a_nI= -AB_(n-1) These relations are equivalent with: B_0=I B_1=A+a_1I B_2=A^2+Aa_1+a_2I ......... B_(n-1)=A^(n-1)+A^(n-2)a_1+...+a_(n-1)I 0 =A^n+A^(n-1)a_1+...+Aa_(n-1)+a_nI The last relation is in fact Phi(A)=0 and the proof is completed. Otilia Popescu --MAA10603.874687395/ece.rutgers.edu-- From crose Sat Sep 20 19:53:28 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA02296; Sat, 20 Sep 97 19:53:28 EDT Date: Sat, 20 Sep 97 19:53:28 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709202353.AA02296@MOGLI.rutgers.edu> To: 330_543 Subject: problem set Cc: crose@MOGLI.rutgers.edu Status: RO Problem set 2 consists of Chapter 3: P1,P2,P5 & P8 Chapter 4: P1, P2, & P4 It is due on 9/23/97. Cheers Chris Rose From crose Sun Sep 21 10:57:53 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA03071; Sun, 21 Sep 97 10:57:45 EDT Date: Sun, 21 Sep 97 10:57:45 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709211457.AA03071@MOGLI.rutgers.edu> To: chriskly@eden.rutgers.edu, nirajp@eden.rutgers.edu Subject: Re: [Lin Zhou : Re: vci] Cc: 330_543@MOGLI.rutgers.edu, linzhou@ece.rutgers.edu Status: RO That's exactly right Niraj. If you run out of Cs and Ds then you do the rearrangement. The proofs are just for upper bonds (worst cases). Cheers, Chris Rose From nirajp@er6.rutgers.edu Sun Sep 21 01:38:57 1997 Return-Path: Received: from er6.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA02704; Sun, 21 Sep 97 01:38:34 EDT Received: from localhost (nirajp@localhost) by er6.rutgers.edu (8.8.5/8.8.5) with SMTP id AAA09282; Sun, 21 Sep 1997 00:45:14 -0400 (EDT) Date: Sun, 21 Sep 1997 00:45:14 -0400 (EDT) From: Niraj Prabhavalkar To: Christine Kleiwerda Cc: 330_543@MOGLI.rutgers.edu, linzhou@ece.rutgers.edu Subject: Re: [Lin Zhou : Re: vci] In-Reply-To: Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO hi about the rearrangement thing, i have one serious doubt. in the book they say that we keep the chain going and keep finding c's and d's to replace each other till we reach the end of the chain. however is it possible that we run out of c's and d's before we run out of the rows and columns??? in that case the upperbound will depend on the no of c's/d's that are available and not necessarily on the min(r1,r3)-1. anyone agrees or disagrees? niraj. $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ NIRAJ PRABHAVALKAR:- US HOUSING US MAILING ADD. PERMANENT ADDRESS BUELL 385 B.P.O 23952 44, POORNANAND BUSCH CAMPUS PO BOX 1119 WALKESHWAR RUTGERS UNIVERSITY PISCATAWAY BOMBAY 400006 NEW BRUNSWICK NJ 08855-1119 INDIA. NEW JERSEY 08855 USA USA. TEL: 732-8781648 TEL: 022-3681733/3623561 EMAIL: nirajp@eden.rutgers.edu EMAIL:nirajp@giasbma.vsnl.net.in nirajp@er5.rutgers.edu $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ From crose Sun Sep 21 11:14:48 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA03104; Sun, 21 Sep 97 11:14:21 EDT Date: Sun, 21 Sep 97 11:14:21 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709211514.AA03104@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: ece machine Cc: crose@MOGLI.rutgers.edu Status: RO Hi Folks, The ECE machine seems to be fried. Hopefully it will be fixed by monday. In the mean time, even I cannot get access to the web page (both front AND back doors). I'll make copies of the PS solutions and distribute them in class. I'll also look into moving the web page to a more reliable machine. For some reason ece is flaky. Cheers, sort of, Chris ROse From jsucec@ece.rutgers.edu Mon Sep 22 02:22:14 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA03910; Mon, 22 Sep 97 02:22:00 EDT Received: from localhost (jsucec@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id BAA13344; Mon, 22 Sep 1997 01:24:15 -0400 Date: Mon, 22 Sep 1997 01:24:15 -0400 (EDT) From: John Sucec To: Niraj Prabhavalkar Cc: 330_543@MOGLI.rutgers.edu Subject: Re: vci In-Reply-To: Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO This message is in response to an E-Mail sent below, on the subject of Virtual Circuit Identifier (VCI)... "Virtual" in the case of VCI, refers to the "circuit" part of VCI, not the "identifier" part. This is because in ATM, unlike TDM where there is an actual time slot allocated to a particular connection, communication needs are satisfied on a best effort basis by the network. If the ATM network is healthy, however, end users will not be able to tell the difference between the best effort cell transport mechanism of ATM from an actual TDM circuit. Hence, the ATM connectivity between end users is referred to as a virtual circuit. As far as the VCI changing from time to time, I don't think this is true, at least not in a dynamic sense. Once an ATM connection is established, network switches use cut-through switching to send cells out on the appropriate port based on the VCI field of each cell header. When the switch sends a cell out on the appropriate port, it will write a new value into the VCI field of the cell header. This new value, however, comes from a "look-up" table that functions as a static mapping of the VCI for the incoming cells of each virtual circuit to the appropriate destination port and a VCI value for outgoing cells of each virtual circuit. The VCI values for cells belonging to a particular virtual circuit, therefore, are maintained statically in the RAM of network switches that compose the path of the virtual circuit. Anyway, I believe that is how the VCI field is typically used. I hope this helps. ...John On Fri, 19 Sep 1997, Niraj Prabhavalkar wrote: > hi, > i'm not very sure about the vci concept yet but this is what i think. > its called virtual because it changes from time to time and is not > dependent on the physical link but on the number of active users at a > time. so the address changes accordingly. > another thing is about todays class. i was slightly lost. > can someone tell me about the second and third theorems please. > waiting for a reply > niraj. > > > From jsucec@ece.rutgers.edu Mon Sep 22 02:58:04 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA03929; Mon, 22 Sep 97 02:57:51 EDT Received: from localhost (jsucec@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id CAA13604 for <330_543@MOGLI.rutgers.edu>; Mon, 22 Sep 1997 02:00:07 -0400 Date: Mon, 22 Sep 1997 02:00:06 -0400 (EDT) From: John Sucec To: 330_543@MOGLI.rutgers.edu Subject: Re: vci (fwd) Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Oops, I said that the VCI values for an ATM connection "are stored in the RAM of network switches." I did not mean to imply, however, that the switching of cells is done by looking up VCIs in RAM... The switching done by ATM nodes has to be at the hardware level in order to switch cells at rates required by typical ATM networks. Therefore, once an ATM connection is established (which is CPU and RAM intensive), the cut through switching of cells is performed 'with hardware'. Unfortunately, I do not understand very well the design of ATM switches at the hardware level, so I can't comment much further on how the VCI-in to VCI-out static mapping is maintained and accessed at the 'hardware level' within the switch. ...John ---------- Forwarded message ---------- Date: Mon, 22 Sep 1997 01:24:15 -0400 (EDT) From: John Sucec To: Niraj Prabhavalkar Cc: 330_543@MOGLI.rutgers.edu Subject: Re: vci This message is in response to an E-Mail sent below, on the subject of Virtual Circuit Identifier (VCI)... "Virtual" in the case of VCI, refers to the "circuit" part of VCI, not the "identifier" part. This is because in ATM, unlike TDM where there is an actual time slot allocated to a particular connection, communication needs are satisfied on a best effort basis by the network. If the ATM network is healthy, however, end users will not be able to tell the difference between the best effort cell transport mechanism of ATM from an actual TDM circuit. Hence, the ATM connectivity between end users is referred to as a virtual circuit. As far as the VCI changing from time to time, I don't think this is true, at least not in a dynamic sense. Once an ATM connection is established, network switches use cut-through switching to send cells out on the appropriate port based on the VCI field of each cell header. When the switch sends a cell out on the appropriate port, it will write a new value into the VCI field of the cell header. This new value, however, comes from a "look-up" table that functions as a static mapping of the VCI for the incoming cells of each virtual circuit to the appropriate destination port and a VCI value for outgoing cells of each virtual circuit. The VCI values for cells belonging to a particular virtual circuit, therefore, are maintained statically in the RAM of network switches that compose the path of the virtual circuit. Anyway, I believe that is how the VCI field is typically used. I hope this helps. ...John On Fri, 19 Sep 1997, Niraj Prabhavalkar wrote: > hi, > i'm not very sure about the vci concept yet but this is what i think. > its called virtual because it changes from time to time and is not > dependent on the physical link but on the number of active users at a > time. so the address changes accordingly. > another thing is about todays class. i was slightly lost. > can someone tell me about the second and third theorems please. > waiting for a reply > niraj. > > > From nirajp@er6.rutgers.edu Sun Sep 21 01:38:57 1997 Return-Path: Received: from er6.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA02704; Sun, 21 Sep 97 01:38:34 EDT Received: from localhost (nirajp@localhost) by er6.rutgers.edu (8.8.5/8.8.5) with SMTP id AAA09282; Sun, 21 Sep 1997 00:45:14 -0400 (EDT) Date: Sun, 21 Sep 1997 00:45:14 -0400 (EDT) From: Niraj Prabhavalkar To: Christine Kleiwerda Cc: 330_543@MOGLI.rutgers.edu, linzhou@ece.rutgers.edu Subject: Re: [Lin Zhou : Re: vci] In-Reply-To: Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO hi about the rearrangement thing, i have one serious doubt. in the book they say that we keep the chain going and keep finding c's and d's to replace each other till we reach the end of the chain. however is it possible that we run out of c's and d's before we run out of the rows and columns??? in that case the upperbound will depend on the no of c's/d's that are available and not necessarily on the min(r1,r3)-1. anyone agrees or disagrees? niraj. $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ NIRAJ PRABHAVALKAR:- US HOUSING US MAILING ADD. PERMANENT ADDRESS BUELL 385 B.P.O 23952 44, POORNANAND BUSCH CAMPUS PO BOX 1119 WALKESHWAR RUTGERS UNIVERSITY PISCATAWAY BOMBAY 400006 NEW BRUNSWICK NJ 08855-1119 INDIA. NEW JERSEY 08855 USA USA. TEL: 732-8781648 TEL: 022-3681733/3623561 EMAIL: nirajp@eden.rutgers.edu EMAIL:nirajp@giasbma.vsnl.net.in nirajp@er5.rutgers.edu $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ From crose Mon Sep 22 12:03:29 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA04263; Mon, 22 Sep 97 12:01:29 EDT Date: Mon, 22 Sep 97 12:01:29 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709221601.AA04263@MOGLI.rutgers.edu> To: jsucec@ece.rutgers.edu, nirajp@eden.rutgers.edu Subject: Re: vci Cc: 330_543@MOGLI.rutgers.edu Status: RO Nice explanation John! From shahid@er7.rutgers.edu Mon Sep 22 15:18:00 1997 Return-Path: Received: from er7.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA04449; Mon, 22 Sep 97 15:16:34 EDT Received: from localhost (shahid@localhost) by er7.rutgers.edu (8.8.5/8.8.5) with SMTP id OAA17663 for <330_543@MOGLI.rutgers.edu>; Mon, 22 Sep 1997 14:23:00 -0400 (EDT) Date: Mon, 22 Sep 1997 14:22:59 -0400 (EDT) From: Shahid Kagal To: 330_543@MOGLI.rutgers.edu Subject: CHAPTER :3 : Page 74 & Crosspoint count + Crosspoint complexity Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Professor Rose, I have doubts regarding the following : 1.On page 74 of text book under the topic of Recursive Construction of Switching Networks there is a calculation for crosspoint complexity.How does 6^l appear in the expression. 2.I have a slight confusion regarding calculation of crosspoint count and crosspoint complexity.If you could explain taking example of a specific network that would be better. Waiting for your quick reply, Thank You. Shahid From crose@localhost.localdomain Mon Sep 22 17:03:13 1997 Return-Path: Received: from localhost.localdomain (ppp-72.ts-11.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA04624; Mon, 22 Sep 97 16:58:57 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id PAA06872; Mon, 22 Sep 1997 15:55:43 -0400 Date: Mon, 22 Sep 1997 15:55:43 -0400 From: Christopher Rose Message-Id: <199709221955.PAA06872@localhost.localdomain> To: 330_543@MOGLI.rutgers.edu, shahid@eden.rutgers.edu Subject: Re: CHAPTER :3 : Page 74 & Crosspoint count + Crosspoint complexity Status: RO Hi, You'll need to state your question (for part 2). As for the 6^l, think about where the recursion has to stop in going from equation 3.7.3 to 3.7.4 (look at the F() term argument). But in general, you'll be able to help everyone if you spell out your question in gory detail. Sometimes you'll spell it out wrong and taht will be an immediately recognizable source of the confusion which as a group we can address and from which we can benefit. Cheers, Chris Rose From shahid@er3.rutgers.edu Tue Sep 23 15:54:26 1997 X-UIDL: e4fc0560f1da072cf4cdc25bb60f5f3a Return-Path: Received: from er3.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA06087; Tue, 23 Sep 97 15:50:57 EDT Received: from localhost (shahid@localhost) by er3.rutgers.edu (8.8.5/8.8.5) with SMTP id OAA21898 for <330_543@MOGLI.rutgers.edu>; Tue, 23 Sep 1997 14:57:12 -0400 (EDT) Date: Tue, 23 Sep 1997 14:57:11 -0400 (EDT) From: Shahid Kagal To: 330_543@MOGLI.rutgers.edu Subject: Calculation of Crosspoint Complexity Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Professor Rose, I wish to know how to calculate crosspoint complexity of a given network like : Point to Point, 3-Stage Clos network :a) Strict Sense Non Blocking and b) Rearrangably non blocking. I thought it was dependent upon the number of switching stages, number of switches in each stage and number of inputs and outputs. But I cannot find a proper answer . Thank You, Shahid. From crose Tue Sep 23 17:09:04 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA06246; Tue, 23 Sep 97 17:06:40 EDT Date: Tue, 23 Sep 97 17:06:40 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709232106.AA06246@MOGLI.rutgers.edu> To: shahid@eden.rutgers.edu Subject: Re: Calculation of Crosspoint Complexity Cc: 330_543 Status: RO It is! BUt it's also dependent upon how you factor the network. That is, I don't believe anyone knows EXACTLY the minimum number of crosspoints one must use except for the most basic networks (or regular ones like Clos, etc). Cheers, Chris ROse From crose Tue Sep 23 21:40:15 1997 X-UIDL: 493e75b84842bad940e63569aa3dec0a Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA06623; Tue, 23 Sep 97 21:37:29 EDT Date: Tue, 23 Sep 97 21:37:29 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709240137.AA06623@MOGLI.rutgers.edu> To: 330_543 Subject: web stuff Status: RO Hi Folks, I've posted the solutions to problem set 2 on the web (hooray for Wenfeng!) I've also made a duplicate of the web page on a winlab machine so that just in case ece goes down, you can still get at the stuff http:/winwww.rutgers.edu/pub/about/people/crose/winlab543.html is the URL. Not everything works (like the signup for instance), but the PS files are there and readable as well as the email archive (which will be updated with your mailings in my absence so keep an eye out for it). See you when I get back (10/2). I should have the exams graded about a week from then is not sooner. Remember, there's no class on 9/30, unless you'd just like to watch the other students in 501 suffer! :) Cheers Chris Rose PS: Anybody know how to get from the airport in Budapest to local hotels? I've not a clue! From crose Tue Sep 23 22:50:27 1997 X-UIDL: f5ce9d185a9515d6d0764f4d1f5b2189 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA06815; Tue, 23 Sep 97 22:43:19 EDT Date: Tue, 23 Sep 97 22:43:19 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709240243.AA06815@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: signup Status: RO Even the signup now works on winlab. So everything should be ok! Cheers, and good luck on the exams! Chris Rose From nirajp@er4.rutgers.edu Wed Sep 24 10:09:35 1997 Return-Path: Received: from eden-backend.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA00198; Wed, 24 Sep 97 10:09:29 EDT Received: from er4.rutgers.edu (nirajp@er4.rutgers.edu [165.230.180.142]) by eden-backend.rutgers.edu (8.8.5/8.8.5) with ESMTP id AAA03049 for ; Wed, 24 Sep 1997 00:32:37 -0400 (EDT) Received: from localhost (nirajp@localhost) by er4.rutgers.edu (8.8.5/8.8.5) with SMTP id AAA03910 for ; Wed, 24 Sep 1997 00:29:18 -0400 (EDT) Date: Wed, 24 Sep 1997 00:29:18 -0400 (EDT) From: Niraj Prabhavalkar To: Christopher Rose Subject: Re: ch 3 In-Reply-To: <9709240137.AA06623@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO hi i have a few questions and doubts. 1. in recursive factorisation something is said about factoring N into prime factors for optimization in case of RNB. could someone give me an ex. of factoring say N=100 or 200 into prime factors. 2. In todays class chris said that The max no of stages in RNB is k-1. i feel actually the max # of successive factorizations are k-1 and the no. of stages are in fact 2logN-1 viz. 2k-1. 3. in recursive factorization for ssnb the initial math is easy to follow but i didnt get the last step. >From F(N) = (2^n)(6^l)F(2) how do we get the last step. basically how does 6^l become logN^(log6) i would appreciate if someone helped soon. niraj. From aonweller@maerskdata-usa.com Wed Sep 24 10:12:56 1997 Return-Path: Received: from msrvr.maerskdata-usa.com by MOGLI.rutgers.edu (4.1/25-eef) id AA00212; Wed, 24 Sep 97 10:12:53 EDT Received: from [10.1.25.41] ([207.242.160.66]) by msrvr.maerskdata-usa.com (Netscape Mail Server v2.02) with SMTP id AAA40; Wed, 24 Sep 1997 11:30:45 +0000 Message-Id: <3428F94C.605C@maerskdata-usa.com> Date: Wed, 24 Sep 1997 07:28:13 -0400 From: aonweller@maerskdata-usa.com (Allen Onweller) X-Mailer: Mozilla 3.01-C-MACOS8 (Macintosh; I; PPC) Mime-Version: 1.0 To: Christopher Rose Cc: 330_501@MOGLI.rutgers.edu, 330_543@MOGLI.rutgers.edu Subject: Problems with alternate 543 Web Site? References: <9709240243.AA06815@MOGLI.rutgers.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO I think that the correct URL is: http://winwww.rutgers.edu/pub/about/people/staff/crose/winlab543.html From aonweller@maerskdata-usa.com Wed Sep 24 10:19:54 1997 Return-Path: Received: from msrvr.maerskdata-usa.com by MOGLI.rutgers.edu (4.1/25-eef) id AA00231; Wed, 24 Sep 97 10:19:46 EDT Received: from mxwnetf3 ([207.242.160.66]) by msrvr.maerskdata-usa.com (Netscape Mail Server v2.02) with SMTP id AAA138; Wed, 24 Sep 1997 13:29:17 +0000 Message-Id: <34291457.4E40@maerskdata-usa.com> Date: Wed, 24 Sep 1997 09:23:35 -0400 From: aonweller@maerskdata-usa.com (Allen Onweller) X-Mailer: Mozilla 3.01 (WinNT; U) Mime-Version: 1.0 To: crose@MOGLI.rutgers.edu Cc: 330_543@MOGLI.rutgers.edu Subject: Bad URL for alternate web site? Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO I think that the correct URL for the alternat 330:543 site is: http://winwww.rutgers.edu/pub/about/people/staff/crose/winlab543.html Regards, Allen From crose Wed Sep 24 11:20:06 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00362; Wed, 24 Sep 97 11:18:46 EDT Date: Wed, 24 Sep 97 11:18:46 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709241518.AA00362@MOGLI.rutgers.edu> To: crose@MOGLI.rutgers.edu, nirajp@eden.rutgers.edu Subject: Re: ch 3 Cc: 330_543 Status: RO on point 2 ... I don't THINK I said the number of stages is k-1. The number of successive factorizations is k-1... which leads to the 2k-1 stages. If you check your notes, I think you'll see we indeed ended up with 2k-1 stages with N/2 switches in each. 6^l = (2^log6)^l = 2^(l log 6) but N = 2^k = 2^(2^l) log N = 2^l so 6^l = (2^l)^(log 6) = (logN)^(log6) I fyou remember, I left the exact relationship open by using an alpha in the exponenet for the logN. Hope that helps. Somebody out there should provide a factorization for your first question Cheers Chris Rose From SIZE=433@att.com Wed Sep 24 11:24:17 1997 Return-Path: Received: from att.com (cagw1.att.com) by MOGLI.rutgers.edu (4.1/25-eef) id AA00383; Wed, 24 Sep 97 11:24:15 EDT Received: by cagw1.att.com; Wed Sep 24 10:25 EDT 1997 Received: from localhost (localhost) by caig1.att.att.com (AT&T/GW-1.0) with internal id KAA16226; Wed, 24 Sep 1997 10:21:58 -0400 (EDT) Date: Wed, 24 Sep 1997 10:21:58 -0400 (EDT) From: Mail Delivery Subsystem Message-Id: <199709241421.KAA16226@caig1.att.att.com> To: crose@MOGLI.rutgers.edu Mime-Version: 1.0 Content-Type: multipart/report; report-type=delivery-status; boundary="KAA16226.875110918/caig1.att.att.com" Subject: Returned mail: Service unavailable Auto-Submitted: auto-generated (failure) Status: RO This is a MIME-encapsulated message --KAA16226.875110918/caig1.att.att.com The original message was received at Wed, 24 Sep 1997 10:21:36 -0400 (EDT) from nuucp@localhost ----- The following addresses had permanent fatal errors ----- ustad.att.com!rice ustad.att.com!jdodley ----- Transcript of session follows ----- ... while talking to ustad.ho.att.com.: >>> MAIL From: SIZE=333 <<< 554 Cannot bind to domain ustaddomain: can't communicate with ypbind 554 ustad.att.com!rice,ustad.att.com!jdodley... Service unavailable --KAA16226.875110918/caig1.att.att.com Content-Type: message/delivery-status Reporting-MTA: dns; caig1.att.att.com Arrival-Date: Wed, 24 Sep 1997 10:21:36 -0400 (EDT) Final-Recipient: RFC822; rice@ustad.ho.att.com Action: failed Status: 5.0.0 Remote-MTA: DNS; ustad.ho.att.com Diagnostic-Code: SMTP; 554 Cannot bind to domain ustaddomain: can't communicate with ypbind Last-Attempt-Date: Wed, 24 Sep 1997 10:21:57 -0400 (EDT) Final-Recipient: RFC822; jdodley@ustad.ho.att.com Action: failed Status: 5.0.0 Remote-MTA: DNS; ustad.ho.att.com Diagnostic-Code: SMTP; 554 Cannot bind to domain ustaddomain: can't communicate with ypbind Last-Attempt-Date: Wed, 24 Sep 1997 10:21:57 -0400 (EDT) --KAA16226.875110918/caig1.att.att.com Content-Type: message/rfc822 Return-Path: Received: (from nuucp@localhost) by caig1.att.att.com (AT&T/GW-1.0) id KAA16163; Wed, 24 Sep 1997 10:21:36 -0400 (EDT) >Received: by cagw1.att.com; Wed Sep 24 10:24 EDT 1997 Received: by cagw1.att.com; Wed Sep 24 10:24 EDT 1997 Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00375; Wed, 24 Sep 97 11:21:54 EDT Date: Wed, 24 Sep 97 11:21:54 EDT From: Christopher Rose Message-Id: <9709241521.AA00375@MOGLI.rutgers.edu> To: aonweller@maerskdata-usa.com Subject: Re: Problems with alternate 543 Web Site? Cc: 330_501@MOGLI.rutgers.edu, 330_543@MOGLI.rutgers.edu Content-Type: text What URL did I provide? Regardless, what you have looks right. You can also reach it by going to my home page http:/winwww.rutgers.edu/pub/about/people/staff/crose/crose.html and following the links at the bottom of the page Cheers, ALL --KAA16226.875110918/caig1.att.att.com-- From crose Wed Sep 24 11:24:50 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00375; Wed, 24 Sep 97 11:21:54 EDT Date: Wed, 24 Sep 97 11:21:54 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709241521.AA00375@MOGLI.rutgers.edu> To: aonweller@maerskdata-usa.com Subject: Re: Problems with alternate 543 Web Site? Cc: 330_501, 330_543 Status: RO What URL did I provide? Regardless, what you have looks right. You can also reach it by going to my home page http:/winwww.rutgers.edu/pub/about/people/staff/crose/crose.html and following the links at the bottom of the page Cheers, ALL From SIZE=996@att.com Wed Sep 24 11:33:31 1997 Return-Path: Received: from att.com (cagw1.att.com) by MOGLI.rutgers.edu (4.1/25-eef) id AA00424; Wed, 24 Sep 97 11:33:31 EDT Received: by cagw1.att.com; Wed Sep 24 10:35 EDT 1997 Received: from localhost (localhost) by caig1.att.att.com (AT&T/GW-1.0) with internal id KAA19966; Wed, 24 Sep 1997 10:31:26 -0400 (EDT) Date: Wed, 24 Sep 1997 10:31:26 -0400 (EDT) From: Mail Delivery Subsystem Message-Id: <199709241431.KAA19966@caig1.att.att.com> To: crose@MOGLI.rutgers.edu Mime-Version: 1.0 Content-Type: multipart/report; report-type=delivery-status; boundary="KAA19966.875111486/caig1.att.att.com" Subject: Returned mail: Service unavailable Auto-Submitted: auto-generated (failure) Status: RO This is a MIME-encapsulated message --KAA19966.875111486/caig1.att.att.com The original message was received at Wed, 24 Sep 1997 10:31:18 -0400 (EDT) from nuucp@localhost ----- The following addresses had permanent fatal errors ----- ustad.att.com!rice ustad.att.com!jdodley ----- Transcript of session follows ----- ... while talking to ustad.ho.att.com.: >>> MAIL From: SIZE=896 <<< 554 Cannot bind to domain ustaddomain: can't communicate with ypbind 554 ustad.att.com!rice,ustad.att.com!jdodley... Service unavailable --KAA19966.875111486/caig1.att.att.com Content-Type: message/delivery-status Reporting-MTA: dns; caig1.att.att.com Arrival-Date: Wed, 24 Sep 1997 10:31:18 -0400 (EDT) Final-Recipient: RFC822; rice@ustad.ho.att.com Action: failed Status: 5.0.0 Remote-MTA: DNS; ustad.ho.att.com Diagnostic-Code: SMTP; 554 Cannot bind to domain ustaddomain: can't communicate with ypbind Last-Attempt-Date: Wed, 24 Sep 1997 10:31:26 -0400 (EDT) Final-Recipient: RFC822; jdodley@ustad.ho.att.com Action: failed Status: 5.0.0 Remote-MTA: DNS; ustad.ho.att.com Diagnostic-Code: SMTP; 554 Cannot bind to domain ustaddomain: can't communicate with ypbind Last-Attempt-Date: Wed, 24 Sep 1997 10:31:26 -0400 (EDT) --KAA19966.875111486/caig1.att.att.com Content-Type: message/rfc822 Return-Path: Received: (from nuucp@localhost) by caig1.att.att.com (AT&T/GW-1.0) id KAA19903; Wed, 24 Sep 1997 10:31:18 -0400 (EDT) >Received: by cagw1.att.com; Wed Sep 24 10:34 EDT 1997 Received: by cagw1.att.com; Wed Sep 24 10:34 EDT 1997 Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00403; Wed, 24 Sep 97 11:31:28 EDT Date: Wed, 24 Sep 97 11:31:28 EDT From: Christopher Rose Message-Id: <9709241531.AA00403@MOGLI.rutgers.edu> To: 330_501@MOGLI.rutgers.edu, 330_543@MOGLI.rutgers.edu Subject: ARRRRRRRGGGGGGGGGGHHHHHHH!!! Cc: crose@MOGLI.rutgers.edu Content-Type: text Hi Folks, I left out a protion of the path for the alternate site url It should have read: http:/winwww.rutgers.edu/pub/about/people/staff/crose/winlabXXX.html where XXX is either 501 or 543. Sorry bout that.... Allen Onweller bailed me out on that one. Thanks Also, for 501 students. GIF files for the old midterm and solutions don't exist! Sorry for the inconvenience. You can always print them out at RU. But a better idea is to follow the links provided to get some ghostview software which you can load on your PC to view postscript files. I've never tried it, but also there's adobe acrobat which I would think should be able to view Postscript somehow (same company which puts out adobe postscript, no?) Cheers ALL I leave today. Let's hope I can avoid a flight 800 sort of deal :) --KAA19966.875111486/caig1.att.att.com-- From crose Wed Sep 24 11:33:42 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00403; Wed, 24 Sep 97 11:31:28 EDT Date: Wed, 24 Sep 97 11:31:28 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9709241531.AA00403@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: ARRRRRRRGGGGGGGGGGHHHHHHH!!! Cc: crose@MOGLI.rutgers.edu Status: RO Hi Folks, I left out a protion of the path for the alternate site url It should have read: http:/winwww.rutgers.edu/pub/about/people/staff/crose/winlabXXX.html where XXX is either 501 or 543. Sorry bout that.... Allen Onweller bailed me out on that one. Thanks Also, for 501 students. GIF files for the old midterm and solutions don't exist! Sorry for the inconvenience. You can always print them out at RU. But a better idea is to follow the links provided to get some ghostview software which you can load on your PC to view postscript files. I've never tried it, but also there's adobe acrobat which I would think should be able to view Postscript somehow (same company which puts out adobe postscript, no?) Cheers ALL I leave today. Let's hope I can avoid a flight 800 sort of deal :) From andyy@ece.rutgers.edu Tue Oct 7 16:37:09 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA16198; Tue, 7 Oct 97 16:37:08 EDT Received: (from andyy@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) id PAA27048 for crose@mogli.rutgers.edu; Tue, 7 Oct 1997 15:36:47 -0400 Date: Tue, 7 Oct 1997 15:36:47 -0400 From: Wingho Yuen Message-Id: <199710071936.PAA27048@ece.rutgers.edu> To: crose@mogli.rutgers.edu Subject: ee 543 Content-Length: 143 Status: RO Hello Prof Rose Would the Cantor Network be covered? I could not follow the proof of the SSNB property of Cantor Network. Thanks Andy Yuen From crose Tue Oct 7 20:38:08 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA16406; Tue, 7 Oct 97 20:37:59 EDT Date: Tue, 7 Oct 97 20:37:59 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710080037.AA16406@MOGLI.rutgers.edu> To: andyy@ece.rutgers.edu Subject: Re: ee 543 Cc: 330_543 Status: RO Nope, don't worry about Cantor. It's much ado about not too much :) Cheers, Chris Rose From linzhou@ece.rutgers.edu Sun Oct 12 16:39:34 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA22433; Sun, 12 Oct 97 16:39:12 EDT Received: from localhost (linzhou@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id PAA06216; Sun, 12 Oct 1997 15:37:55 -0400 Date: Sun, 12 Oct 1997 15:37:55 -0400 (EDT) From: Lin Zhou To: Christopher Rose Cc: andyy@ece.rutgers.edu, 330_543@MOGLI.rutgers.edu Subject: Re: ee 543 In-Reply-To: <9710080037.AA16406@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Dr. Rose, In last class, you said the power of inverse Banyan network which forms compact superconcentrator was (n/2)*(logn)*2. Since the total number of delta switch is (n/2)*(logn), connection pattern is exp2((n/2)*logn). Why the power is doubled to (n/2)*(log)*2 ? zhou lin From crose Sun Oct 12 17:52:36 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA22488; Sun, 12 Oct 97 17:51:54 EDT Date: Sun, 12 Oct 97 17:51:54 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710122151.AA22488@MOGLI.rutgers.edu> To: crose@MOGLI.rutgers.edu, linzhou@ece.rutgers.edu Subject: Re: ee 543 Cc: 330_543@MOGLI.rutgers.edu, andyy@ece.rutgers.edu Status: RO Hi, Just after the class was over, I saw that I'd counted switch states in once case and delta switches in the other. Each delta switch has two states (cross and straight). The number 2N log N for multicast is the number of SWITCHES but the number of cross points (which we kind of us analogously to switch states) is 4N log N (just like the number of switch states for a Benes network is on the order of 2N log N (while the number of switches is of order N log N). Cheers Chris Rose From crose Sun Oct 12 17:52:36 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA22488; Sun, 12 Oct 97 17:51:54 EDT Date: Sun, 12 Oct 97 17:51:54 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710122151.AA22488@MOGLI.rutgers.edu> To: crose@MOGLI.rutgers.edu, linzhou@ece.rutgers.edu Subject: Re: ee 543 Cc: 330_543@MOGLI.rutgers.edu, andyy@ece.rutgers.edu Status: RO Hi, Just after the class was over, I saw that I'd counted switch states in once case and delta switches in the other. Each delta switch has two states (cross and straight). The number 2N log N for multicast is the number of SWITCHES but the number of cross points (which we kind of us analogously to switch states) is 4N log N (just like the number of switch states for a Benes network is on the order of 2N log N (while the number of switches is of order N log N). Cheers Chris Rose From linzhou@ece.rutgers.edu Sun Oct 12 18:32:47 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA22520; Sun, 12 Oct 97 18:32:15 EDT Received: from localhost (linzhou@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id RAA10124; Sun, 12 Oct 1997 17:30:59 -0400 Date: Sun, 12 Oct 1997 17:30:58 -0400 (EDT) From: Lin Zhou To: Christopher Rose Cc: 330_543@MOGLI.rutgers.edu, andyy@ece.rutgers.edu Subject: Re: ee 543 In-Reply-To: <9710122151.AA22488@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Dear Dr. Rose, Thank you for your explanation on the number of switches and the number of states. So the number of connection pattern is the number of states, while the power of connection pattern is the number of delta swiches. You said the number of crosspoints is "analogously the number of states. Is this the actualy number of crosspoints? For instance, P2P delta switch has 2 states, only two crosspoints is enough? As I understand, four crosspoints is used for 2x2 switch, but two states exists.(one control bit). Please give me the answer. Thanks a lot. Best regards, zhou lin On Sun, 12 Oct 1997, Christopher Rose wrote: > Hi, > > Just after the class was over, I saw that I'd counted > switch states in once case and delta switches in the other. > Each delta switch has two states (cross and straight). > > The number 2N log N for multicast is the number of SWITCHES > but the number of cross points (which we kind of us analogously > to switch states) is 4N log N (just like the number of switch states > for a Benes network is on the order of 2N log N (while the number > of switches is of order N log N). > > Cheers > > Chris Rose > From crose Sun Oct 12 23:06:16 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA22763; Sun, 12 Oct 97 23:06:00 EDT Date: Sun, 12 Oct 97 23:06:00 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710130306.AA22763@MOGLI.rutgers.edu> To: crose@MOGLI.rutgers.edu, linzhou@ece.rutgers.edu Subject: Re: ee 543 Cc: 330_543@MOGLI.rutgers.edu, andyy@ece.rutgers.edu Status: RO My Goodness, I think I must have been asleep. I just reread what I wrote. Here's the low down... Each connection pattern corresponds to (at least one) switch state. The power of a switch is the log number of connection patterns. You need at least log_2( switch power) crosspoints to realize a switch with a given number of connection patterns. Or another way to think about it is that you need at least that many delta switches (since like crosspoints, they have only two states). Hope that clarifies my ambiguous/wrong previous statement! Cheers, Chris Rose PS: What I did in class at the end (the board to the far left) was DEAD WRONG. You cannot take each delta switch and multiply by two to get the switch states. Not sure what I was thinking... AAAAAARRRRRRRRGGGGGGGGGG! Why? Because the number of switch STATES is 2^(number of binary decision elements) in the switch. Just to be careful, remember that the number of switch states is not necessarily the number of switching patterns! That's what I get for rushing at the end of class! Thanks for persisting in your question. From crose@localhost.localdomain Mon Oct 13 10:12:41 1997 Return-Path: Received: from localhost.localdomain (ppp-72.ts-4.nyc.idt.net) by boom.rutgers.edu (4.1/SMI-4.1) id AA01950; Mon, 13 Oct 97 10:12:39 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id KAA00761; Mon, 13 Oct 1997 10:00:22 -0400 Date: Mon, 13 Oct 1997 10:00:22 -0400 From: Christopher Rose Message-Id: <199710131400.KAA00761@localhost.localdomain> To: 330_543@mogli.rutgers.edu Subject: grading Cc: crose@boom.rutgers.edu Status: RO Hi Folks, I"m done the grading for the 543 exam. The TA (Wenfeng) will collate the results and we'll return them on Tuesday. In all, I'm pretty pleased, except for the fact that most of you know very little probability... but that's correctable :) Cheers, Chris Rose From crose@localhost.localdomain Mon Oct 13 11:07:50 1997 Return-Path: Received: from localhost.localdomain (ppp-72.ts-4.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA23751; Mon, 13 Oct 97 11:07:13 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id KAA00761; Mon, 13 Oct 1997 10:00:22 -0400 Date: Mon, 13 Oct 1997 10:00:22 -0400 From: Christopher Rose Message-Id: <199710131400.KAA00761@localhost.localdomain> To: 330_543@mogli.rutgers.edu Subject: grading Cc: crose@MOGLI.rutgers.edu Status: RO Hi Folks, I"m done the grading for the 543 exam. The TA (Wenfeng) will collate the results and we'll return them on Tuesday. In all, I'm pretty pleased, except for the fact that most of you know very little probability... but that's correctable :) Cheers, Chris Rose From crose Wed Oct 15 11:21:04 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA26625; Wed, 15 Oct 97 11:20:43 EDT Date: Wed, 15 Oct 97 11:20:43 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710151520.AA26625@MOGLI.rutgers.edu> To: 330_543 Subject: "proof" Cc: crose@MOGLI.rutgers.edu Status: RO Hi Folks, I hate my "proof" or ssnb for multipoint networks when viewed in the light of day. I'm convinced we need no more than $N$ centerstage switches (because the overlap argument does not hold water... if n_3-1 inputs are busy in the output stage switch and N-1 outputs are busy in the input stage switch, then THERE MUST BE OVERLAP (Salim Manji, I need to see your exam again). That is, those $n_3-1$ lines MUST BE completely included in the paths radiating from the first stage switch. But having opened that door, we need to figure out a tight lower bound (for the box in which we've placed ourselves). That is, is $N$ too many? Since I don't know the answer, let's open a competition. In a non-collaborative way I'd like arguments from each of you for why the number of center stage switches in a multipoint network must be ____. I'd like your answers by friday via email. You can make up a postscript file and mail it or just plain text if possible. This will be worth 10 points on your first quiz grade (which is why I don't want collaboration). Send your submissions to me (crose@mogli.rutgers.edu or crose@ece.rutgers.edu). GOOD LUCK! Cheers, Chris Rose From crose Wed Oct 15 11:23:59 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA26632; Wed, 15 Oct 97 11:23:46 EDT Date: Wed, 15 Oct 97 11:23:46 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710151523.AA26632@MOGLI.rutgers.edu> To: 330_543 Subject: ALSO Status: RO I'll defer posting solutions to that problem (well yes I DO know the answer now, but it's nice to generate excitement, no?) until friday. The other solutions will be available on the web today. Cheers From crose Wed Oct 15 12:15:41 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA26760; Wed, 15 Oct 97 12:11:40 EDT Date: Wed, 15 Oct 97 12:11:40 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710151611.AA26760@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: regrade policy Status: RO Hi Folks, Now that the solutions are out, you have a week to send me your complaints IN WRITING along with your exam. I'll regrade and that grade will be final. Don't hesitate to ask questions throug the regrade process. I'm not an ogre and will probably not dock yoy points on other sections unless I determine I was asleep when I graded them :) Cheers, Chris Rose From alap@winlab.rutgers.edu Wed Oct 15 22:24:32 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA27451; Wed, 15 Oct 97 22:24:31 EDT Received: from gsm.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id VAA07261; Wed, 15 Oct 1997 21:27:12 -0400 Received: by gsm.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id VAA14270; Wed, 15 Oct 1997 21:27:12 -0400 Date: Wed, 15 Oct 1997 21:27:12 -0400 From: alap@winlab.rutgers.edu (Ana Lucia Pinheiro) Message-Id: <199710160127.VAA14270@gsm.winlab.rutgers.edu> To: crose@mogli Subject: Exam problem Status: RO Prof Rose, I have a question about the exam problem: multicast is only one to many and never many to one (?) I understand that all switches must be capable of multicast, not only the switches in the first layer. Is that right ? Thanks a lot. Ana. From crose@localhost.localdomain Wed Oct 15 22:55:37 1997 Return-Path: Received: from localhost.localdomain (ppp-6.ts-9.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA27470; Wed, 15 Oct 97 22:55:17 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id VAA03443 for 330_543@mogli.rutgers.edu; Wed, 15 Oct 1997 21:47:54 -0400 Date: Wed, 15 Oct 1997 21:47:54 -0400 From: Christopher Rose Message-Id: <199710160147.VAA03443@localhost.localdomain> To: 330_543@mogli.rutgers.edu Subject: problem sets Status: RO Hi Folks, Here's a gift from me to you! Problem set 3 (due 10/23/97) Chapter 5 problems 1,2,4 and 5 Problem set 4 (due 10/30/97) Chapter 6 problems 2,3,5,7 and 10 The test is on November 4th (tuesday) in class and beyond (the next period too). Remember to wait for 20minutes tomorrow (thursday) just in case I'm delayed by traffic (or the baby arrives by appointment -- we're hoping hard for the latter, otherwise I've got to repeat this routine next week too :( ) Cheers all Your sleepless professor soon to become sleepless^2 PS: I'm looking to wrap up the descriptive switching stuff pretty quickly so we can get to performance issues. By the way, might you like to read about how a 5ESS works (the AT&T old wonderswitch)? From crose Wed Oct 15 22:58:33 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA27487; Wed, 15 Oct 97 22:58:22 EDT Date: Wed, 15 Oct 97 22:58:22 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710160258.AA27487@MOGLI.rutgers.edu> To: alap@winlab.rutgers.edu Subject: Re: Exam problem Cc: 330_543 Status: RO Yup, all the switches are capable of multicast. However, you can make up your own version of multicast if you like (i.e. you can specify your own box as long as it is SSNB and can provide any multicast pattern AND IS A CLOS network :) You might also consider the issue of wide sense non-blocking where you establish rules for nonblocking behavior (this is harder and i'll double the credit if you can solve this one). Cheers, Chris Rose ******************* Prof Rose, I have a question about the exam problem: multicast is only one to many and never many to one (?) I understand that all switches must be capable of multicast, not only the switches in the first layer. Is that right ? Thanks a lot. Ana. From crose Wed Oct 15 23:02:05 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA27499; Wed, 15 Oct 97 23:01:14 EDT Date: Wed, 15 Oct 97 23:01:14 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710160301.AA27499@MOGLI.rutgers.edu> To: alap@winlab.rutgers.edu Subject: Re: Exam problem Cc: 330_543 Status: RO OH and yes we cannot have many to one (we'll save that loveliness for packet switching) From crose Thu Oct 16 12:40:11 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA28263; Thu, 16 Oct 97 12:39:50 EDT Date: Thu, 16 Oct 97 12:39:50 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710161639.AA28263@MOGLI.rutgers.edu> To: jasonjen@ece.rutgers.edu Subject: Re: Question: NxN multipoint network?! Cc: 330_543 Status: RO The box i'm putting you in is tat any call can use any resources is so desires, even it it's inefficient. Think about what that means on the input side for a multicast switch. From alap@winlab.rutgers.edu Thu Oct 16 16:41:41 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA28553; Thu, 16 Oct 97 16:41:41 EDT Received: from cell.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id PAA18228; Thu, 16 Oct 1997 15:44:14 -0400 Received: by cell.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id PAA19823; Thu, 16 Oct 1997 15:44:13 -0400 Date: Thu, 16 Oct 1997 15:44:13 -0400 From: alap@winlab.rutgers.edu (Ana Lucia Pinheiro) Message-Id: <199710161944.PAA19823@cell.winlab.rutgers.edu> To: crose@MOGLI Subject: Still question... Cc: alap@winlab.rutgers.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Md5: r3eUzTo3PzhGmc6zLqJXPg== Status: RO > > The box i'm putting you in is tat any call can use > any resources is so desires, even it it's inefficient. > So, if I have an empty input I should be able to send to "as many as I want (FREE) outputs". It does not matter HOW. The problem then only changes because now I have the possibility to send either one-to-one and/or one-to-many. That means that if I am braodcasting to many outputs that are in the same switch is the same problem as one-to-one, cause I just get in the switch input with one line and broadcast internally in the switch. Is that correct ? > > You might also consider the issue of wide sense non-blocking where > you establish rules for nonblocking behavior (this is harder and > i'll double the credit if you can solve this one). > Can you explain better what is "wide-sense non blocking" ? Is this the case where I follow some algorithm when I assign paths ? Thanks again. Ana. From crose Thu Oct 16 21:00:46 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA28730; Thu, 16 Oct 97 21:00:45 EDT Date: Thu, 16 Oct 97 21:00:45 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710170100.AA28730@MOGLI.rutgers.edu> To: alap@winlab.rutgers.edu Subject: Re: Still question... Cc: crose@MOGLI.rutgers.edu Status: RO Wide sense non-blocking is a combination of switching hardware and route selection algorithms that render a switch SSNB eventhough it might be only RNB under an uncontrolled routing protocol. Cheers, Chris Rose From crose Thu Oct 16 21:01:34 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA28735; Thu, 16 Oct 97 21:01:11 EDT Date: Thu, 16 Oct 97 21:01:11 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710170101.AA28735@MOGLI.rutgers.edu> To: alap@winlab.rutgers.edu Subject: Re: Still question... Cc: 330_543 Status: RO Wide sense non-blocking is a combination of switching hardware and route selection algorithms that render a switch SSNB eventhough it might be only RNB under an uncontrolled routing protocol. Cheers, Chris Rose From jasonjen@ece.rutgers.edu Thu Oct 16 21:35:40 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA28765; Thu, 16 Oct 97 21:35:39 EDT Received: (from jasonjen@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) id UAA29436 for crose; Thu, 16 Oct 1997 20:33:39 -0400 Date: Thu, 16 Oct 97 20:33:38 EDT From: Jason Jen To: crose@ece.rutgers.edu Subject: More question about NxN ssnb clos network Message-Id: Status: RO Dr. Rose, Hi, is it okay to have only some inputs (say less than N inputs) to perform multicasting so that all N output terminals are active? In this case all idle input terminals cannot make any connection and it's not considered as "blocking". Thanks, Jason Jen From crose Thu Oct 16 22:07:57 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA28807; Thu, 16 Oct 97 22:07:38 EDT Date: Thu, 16 Oct 97 22:07:38 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710170207.AA28807@MOGLI.rutgers.edu> To: jasonjen@ece.rutgers.edu Subject: Re: More question about NxN ssnb clos network Cc: 330_543 Status: RO Dr. Rose, Hi, is it okay to have only some inputs (say less than N inputs) to perform multicasting so that all N output terminals are active? In this case all idle input terminals cannot make any connection and it's not considered as "blocking". Thanks, Well, think about that one. If you're doing multicasting and don't allow an input to be inactive, then you'll end up with more than N connection requests (a no no). Chers, Chris Rose From crose Thu Oct 16 22:09:44 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA28817; Thu, 16 Oct 97 22:09:26 EDT Date: Thu, 16 Oct 97 22:09:26 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710170209.AA28817@MOGLI.rutgers.edu> To: 330_543 Subject: competition Cc: crose@MOGLI.rutgers.edu Status: RO Hi Folks, the doors close on clos-multipoint entries tomorrow (friday) at 12 midnight! It's worth 10 whole points on your first quiz grade! Cheers, Chris Rose From shahid@er4.rutgers.edu Fri Oct 17 12:39:31 1997 X-UIDL: 8f931a26aa4b6cb9a6b9fe5942bc101f Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA29733; Fri, 17 Oct 97 12:39:30 EDT Received: from er4.rutgers.edu (shahid@er4.rutgers.edu [165.230.180.142]) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with ESMTP id LAA07925 for ; Fri, 17 Oct 1997 11:37:22 -0400 Received: from localhost (shahid@localhost) by er4.rutgers.edu (8.8.5/8.8.5) with SMTP id LAA06159 for ; Fri, 17 Oct 1997 11:41:52 -0400 (EDT) Date: Fri, 17 Oct 1997 11:41:52 -0400 (EDT) From: Shahid Kagal To: crose@ece.rutgers.edu Subject: Multipoint NxN network Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Respected Prof. Rose, I have a doubt regarding the question you have put forward. You have written in the mail than there are n-1 inputs active at the output switch and N-1 outputs active at the input switch. But if there are total N inputs than how can we have N-1 outputs from a single switch active or for that matter do you mean outputs from all the first stage switches. If it has something to do with multicasting please explain. Also if I go beyond this point than the N-1 term in the expression (N-1 + n3-1) could according to the proof of SSNB networks mean inputs active at a time in a single first stage switch. Please also correct this interpretation if wrong. ( or I have confused the symbols) Thank You, Shahid. From crose Fri Oct 17 13:26:29 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA29806; Fri, 17 Oct 97 13:26:11 EDT Date: Fri, 17 Oct 97 13:26:11 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710171726.AA29806@MOGLI.rutgers.edu> To: shahid@eden.rutgers.edu Subject: Re: Multipoint NxN network Cc: 330_543 Status: RO YOU WROTE ************** I have a doubt regarding the question you have put forward. You have written in the mail than there are n-1 inputs active at the output switch and N-1 outputs active at the input switch. But if there are total N inputs than how can we have N-1 outputs from a single switch active or for that matter do you mean outputs from all the first stage switches. If it has something to do with multicasting please explain. Also if I go beyond this point than the N-1 term in the expression (N-1 + n3-1) could according to the proof of SSNB networks mean inputs active at a time in a single first stage switch. Please also correct this interpretation if wrong. ( or I have confused the symbols) ************************ COnsider this: What if the first input wants to sent info to N-1 outputs in a broadcast fashion. Can he/she set up N-1 paths through the first stage switch? (yes). Now, just to throw a monkey wrench in things. Suppose that you DON'T allow first stage multicast and only permit it at the second stage and later. How might this change the problem. Is the switch now blocking!?!?!? I want you all to think carefullly about your assumptions (many of you already have... thanks) and provide an answer! :) Cheers, From aonweller@maerskdata-usa.com Fri Oct 17 14:57:16 1997 Return-Path: Received: from msrvr.maerskdata-usa.com by MOGLI.rutgers.edu (4.1/25-eef) id AA00180; Fri, 17 Oct 97 14:57:16 EDT Received: from mxwnetf3 ([207.242.160.66]) by msrvr.maerskdata-usa.com (Netscape Mail Server v2.02) with SMTP id AAA141 for ; Fri, 17 Oct 1997 18:02:59 +0000 Message-Id: <3447A6DB.DCC@maerskdata-usa.com> Date: Fri, 17 Oct 1997 13:56:43 -0400 From: aonweller@maerskdata-usa.com (Allen Onweller) X-Mailer: Mozilla 3.01 (WinNT; U) Mime-Version: 1.0 To: Christopher Rose Subject: Re: Multipoint NxN network References: <9710171726.AA29806@MOGLI.rutgers.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO Christopher Rose wrote: > > COnsider this: > > What if the first input wants to sent info to N-1 outputs > in a broadcast fashion. Can he/she set up N-1 paths > through the first stage switch? (yes). >.... Hello Professor Rose, I am sticking to my original submission for the extra credit, but I have a few comments with respect to your last e-mail: I'm not sure if I'm missing something obvious, but: If you mean a total of N-1 paths through the network I agree. But I tend to disagree that an single input can setup N-1 paths through the first stage in general. I would argue that it can set up at most n_1 paths where n_1 is the number of outputs from a first stage switch. After that, the second and/or third stages are needed to connect the remaining paths. Of course if n_1 = N, then your statement holds. Maybe this was implied in you discussion. Something that I need to look into further is: Ignoring fan out problems, if n_1 = N, do we really need a third stage? Or for that matter a second stage? Obviously it wouldn't be a Clos net without those stages. (Perhaps by tying corresponding outputs from the first stage together so that each of the N outputs is linked to r_1 lines from the r_1 switches forming a sort of output bus. Of couse bus arbitration would be needed.) Maybe I'll have time to look into this later next week. Regards, Allen From shahid@er4.rutgers.edu Fri Oct 17 15:47:41 1997 Return-Path: Received: from er4.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA00276; Fri, 17 Oct 97 15:47:40 EDT Received: from localhost (shahid@localhost) by er4.rutgers.edu (8.8.5/8.8.5) with SMTP id OAA28199 for ; Fri, 17 Oct 1997 14:50:03 -0400 (EDT) Date: Fri, 17 Oct 1997 14:50:03 -0400 (EDT) From: Shahid Kagal To: Christopher Rose Subject: Re: Multipoint NxN network In-Reply-To: <9710171726.AA29806@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Respected Prof. Rose, I am still a little bit confused. It is correct to suppose that a particular input if wants to broadcast to N-1 outputs will require N-1 paths thru the first stage switch. But does it mean a single switch or all the switches and if the latter than how I cannot figure out. Thank You, Shahid. On Fri, 17 Oct 1997, Christopher Rose wrote: > YOU WROTE > ************** > I have a doubt regarding the question you have put forward. You have > written in the mail than there are n-1 inputs active at the output switch > and N-1 outputs active at the input switch. But if there are total N > inputs than how can we have N-1 outputs from a single switch active or > for that matter do you mean outputs from all the first stage switches. If > it has something to do with multicasting please explain. Also if I go > beyond this point than the N-1 term in the expression (N-1 + n3-1) could > according to the proof of SSNB networks mean inputs active at a time in a > single first stage switch. Please also correct this interpretation if > wrong. ( or I have confused the symbols) > > ************************ > > COnsider this: > > What if the first input wants to sent info to N-1 outputs > in a broadcast fashion. Can he/she set up N-1 paths > through the first stage switch? (yes). > > Now, just to throw a monkey wrench in things. Suppose > that you DON'T allow first stage multicast and only permit it at > the second stage and later. How might this change the problem. > Is the switch now blocking!?!?!? > > I want you all to think carefullly about your assumptions (many of you > already have... thanks) and provide an answer! :) > > Cheers, > From crose@localhost.localdomain Sat Oct 18 03:40:11 1997 Return-Path: Received: from localhost.localdomain (ppp-20.ts-9.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA01037; Sat, 18 Oct 97 03:39:58 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id CAA00920 for 330_543@mogli.rutgers.edu; Sat, 18 Oct 1997 02:32:09 -0400 Date: Sat, 18 Oct 1997 02:32:09 -0400 From: Christopher Rose Message-Id: <199710180632.CAA00920@localhost.localdomain> To: 330_543@mogli.rutgers.edu Subject: submissions Status: RO Submissions are formally closed as of now (2:45AM Saturday 10/18) for the clos multicast competition. I will print the results soon and evaluate your opuses :) From crose@localhost.localdomain Sat Oct 18 16:36:55 1997 Return-Path: Received: from localhost.localdomain (ppp-18.ts-1.nyc.idt.net) by boom.rutgers.edu (4.1/SMI-4.1) id AA02497; Sat, 18 Oct 97 16:36:52 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id QAA01368; Sat, 18 Oct 1997 16:24:17 -0400 Date: Sat, 18 Oct 1997 16:24:17 -0400 From: Christopher Rose Message-Id: <199710182024.QAA01368@localhost.localdomain> To: 330_543@localhost.localdomain Subject: averages Cc: crose@boom.rutgers.edu Status: RO Hi Folks, The class average was 127 +- 23 s.d. The high was 170 and the low was 50. All in all I was pretty pleased. Class average would probably fall somewhere around a low B to a solid B if I had to hand out grades today. Good job for the most part folks. Just have to teach you a bit of probability. Cheers, Chris Rose From crose@localhost.localdomain Sat Oct 18 17:33:16 1997 Return-Path: Received: from localhost.localdomain (ppp-18.ts-1.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA01613; Sat, 18 Oct 97 17:32:33 EDT Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id QAA01373 for 330_543@mogli.rutgers.edu; Sat, 18 Oct 1997 16:24:38 -0400 Date: Sat, 18 Oct 1997 16:24:38 -0400 From: Christopher Rose Message-Id: <199710182024.QAA01373@localhost.localdomain> To: 330_543@mogli.rutgers.edu Subject: averages Status: RO Hi Folks, The class average was 127 +- 23 s.d. The high was 170 and the low was 50. All in all I was pretty pleased. Class average would probably fall somewhere around a low B to a solid B if I had to hand out grades today. Good job for the most part folks. Just have to teach you a bit of probability. Cheers, Chris Rose From xuyang@rutcor.rutgers.edu Fri Oct 24 00:13:11 1997 Return-Path: Received: from bartok.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA08757; Fri, 24 Oct 97 00:12:56 EDT Received: (from xuyang@localhost) by bartok.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.12) id XAA25168 for 330_543@mogli; Thu, 23 Oct 1997 23:14:13 -0400 Date: Thu, 23 Oct 97 23:14:12 EDT From: Yang Xu To: 330_543@mogli Subject: complexity definition? Message-Id: Status: RO Dr. Rose, The complexity is defined on what kind of operations? +, -, * counted as one single operation? How about assignment such as $a[1]\leftarrow 1$? If the assigment is counted as one single operation, then as I remember bucket sort can be completed in linear time when the inputs are some close set of integers. Thanks a lot, yang From alap@winlab.rutgers.edu Thu Oct 23 23:35:55 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA08667; Thu, 23 Oct 97 23:35:34 EDT Received: from gsm.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id WAA05490; Thu, 23 Oct 1997 22:36:53 -0400 Received: by gsm.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id WAA12123; Thu, 23 Oct 1997 22:36:52 -0400 Date: Thu, 23 Oct 1997 22:36:52 -0400 From: alap@winlab.rutgers.edu (Ana Lucia Pinheiro) Message-Id: <199710240236.WAA12123@gsm.winlab.rutgers.edu> To: 330_543@mogli Subject: Sort Complexity Status: RO Prof. Rose, Isn't the complexity of "divide-sort-merge" algorithm NlogN - NC(1) as opposed to N(logN-1) - NC(1) given in class ?? Thanks a lot, Ana. From crose Fri Oct 24 07:25:01 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA08985; Fri, 24 Oct 97 07:24:10 EDT Date: Fri, 24 Oct 97 07:24:10 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710241124.AA08985@MOGLI.rutgers.edu> To: 330_543, xuyang@rutcor.rutgers.edu Subject: Re: complexity definition? Cc: 330_501 Status: RO Hi Yang, Good question! For the merge sort algorithm, the limiting step is the merge since at the bottom of the recursion you can parallelize the comparion operations. The merge takes two ordered lists, a1,a2,a3... and b1,b2,b3 and does the following (for non-decreasing sort) Compare a1 and b1 --> place smaller (if tied take a1) in merged list hold on to larger (call it R) Compare R and next element from the OTHER list -> place smaller in the merged list etc. As you can see, for a list of size N you end up with N comparison operations and THIS is the complexity we're talking about. The factor of logN comes in from the fact that we split the list logN times (recursion) and are therefore doing this merge on N elements logN times. There're also stores going on, but we ignore those or just lump them into the compare. Now as for the actual time complexity in general, that's a little more complex. For example, the time complexity of the algorithm in the book (concatenation of bitonic sorters) is of order (logN)^2 (no factor of N at all if you consider that each stage of sorting (using the 2x2 sorters) takes one unit of time. However, the overall COMPLEXITY is still N (logN)^2 since you have of order N sorters in each stage (N/2 to be exact). So the complexity issue is not just about time. Sorting requires at least N log N complexity no matter how you cut it. If someone says different, then they are misguided or lying to you :) TO answer your question about bucket sort, I'd need to remember bucket sort... BUT I DON'T :) Could you give a brief description to refresh my memory? Thanks. Oh, one last thing, I'm avoiding the guts of comparison at the bit level. That is, you can tell half the time (random integers of fixed maximum size) whether one number is bigger by looking at the first bit, 1/4 of the time you need to look at the second bit also, etc so that the average random comparison takes the examination of only 2 bits. Of course, as your list gets sorted better and better (nonrandom) you've got to compare more bits. Well not quite one last thing: if you want to go deeper into the theory, one could pose the sorting problem as a "twenty questions" game. That is, what is the minimum number of yes no questions you need to ask (binary comparisons you need to perform) to sort a list. Well, if any ordering is equally likely, you've got a uniform distribution on N! possibilities. Identifying which possibility is essentially equivalent to sorting the list. The entropy of a Uniform distribution with N! elements is log(N!) which again is of order N log N. You just can't escape from N log N can you !?!?!?! Cheers, Chris Rose From crose Fri Oct 24 07:26:04 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA08991; Fri, 24 Oct 97 07:25:55 EDT Date: Fri, 24 Oct 97 07:25:55 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710241125.AA08991@MOGLI.rutgers.edu> To: 330_543 Subject: whoops Status: RO Posted this to the wrong group! ******************* Hi Ana, Yup, I made a calculation error in counting the stages. The ORDER of the complexity does not change, but the number of stages of reduction is logN as you pointed out. Thanks for catching that error. Cheers, Chris Rose From xuyang@rutcor.rutgers.edu Fri Oct 24 12:37:17 1997 Return-Path: Received: from rutcor.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA09309; Fri, 24 Oct 97 12:37:17 EDT Received: (from xuyang@localhost) by rutcor.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.12) id LAA18519 for Christopher Rose ; Fri, 24 Oct 1997 11:38:28 -0400 Date: Fri, 24 Oct 97 11:38:28 EDT From: Yang Xu To: Christopher Rose Subject: Re: complexity definition? In-Reply-To: Your message of Fri, 24 Oct 97 07:24:10 EDT Message-Id: Status: RO Dr. Rose, Thanks for your exclusive answer! Yes, it has been shown that comparison based sorting has lower bound of NlogN. Bucket sorting is not comparison based sorting, as I understand. The idea is simple. Suppose we want to sort N numbers(must be integers!) in a list S. Creating an array A with size of O(N), and go over N numbers in list S and assign each $i\in S$ to A[i], i.e. $A[i]\leftarrow i, \forall i\in S$. Then, numbers are sorted in array A. If S is a set(no duplicate), then in each bucket of A there is at most 1 number. If S is not a set, there are maybe several nubmers in one bucket. But it doen't matter too much( we can use a counter for each bucket to record the number of element in each bucket). If we say assigning one number takes logN (actually it is the time to allocate the space A[i], given i), then we end up with magic number NlogN. If we assume finding A[i], given i, takes O(1) time, it is linear algorithm. I am having an algorithm book(by Cormen, et. al) in front of me now! I am sorry that I made a mistake. The algorithm I just described above is actually called counting sort in the book. The book says it uses operations other than comparison and rans in linear time. I think in our switch context, inputs are integers and counting sort is better than quick sort in performance and implementation. Cheers?! yang From linzhou@ece.rutgers.edu Sat Oct 25 14:02:44 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA10416; Sat, 25 Oct 97 14:02:43 EDT Received: from localhost (linzhou@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id MAA02089 for ; Sat, 25 Oct 1997 12:59:07 -0400 Date: Sat, 25 Oct 1997 12:59:07 -0400 (EDT) From: Lin Zhou To: Christopher Rose Subject: proof In-Reply-To: <9710241125.AA08991@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Dear Dr. Rose, When you proved the therom last class, you give the restrictions of input compact and output monotone. For both conditions, it allows increase in cycle? Why you restain the output as d(i+1)>=mod(d(i+1) Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA10760; Sat, 25 Oct 97 22:10:31 EDT Date: Sat, 25 Oct 97 22:10:31 EDT From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710260210.AA10760@MOGLI.rutgers.edu> To: linzhou@ece.rutgers.edu Subject: Re: proof Cc: 330_543 Status: RO That was the issue. The mod condition does not work. It has to be strictly monotone and less then N (remove the mod symbol like I did after Salim made his observation). Cheers, Chris ROse From alap@winlab.rutgers.edu Mon Oct 27 13:10:48 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA12617; Mon, 27 Oct 97 13:10:48 EST Received: from gsm.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id MAA25327; Mon, 27 Oct 1997 12:11:29 -0500 Received: by gsm.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id MAA17373; Mon, 27 Oct 1997 12:11:29 -0500 Date: Mon, 27 Oct 1997 12:11:29 -0500 From: alap@winlab.rutgers.edu (Ana Lucia Pinheiro) Message-Id: <199710271711.MAA17373@gsm.winlab.rutgers.edu> To: crose@mogli Subject: Exam Problem Status: RO Prof. Rose, I would like to know if you graded the exam problem we sent via e-mail. In class you said the answer was N (for SSNB), but what about RNB ? Thnak you very much. Ana. From crose Mon Oct 27 15:45:13 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA12764; Mon, 27 Oct 97 15:45:12 EST Date: Mon, 27 Oct 97 15:45:12 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710272045.AA12764@MOGLI.rutgers.edu> To: tonguc@av.rutgers.edu Subject: Re: abstract Cc: crose@MOGLI.rutgers.edu Status: RO Hi, Thanks! Cheers, Chris PS: not sure what happened before... might I have sent it to Marios only? Who knows... From crose Mon Oct 27 15:48:41 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA12781; Mon, 27 Oct 97 15:48:41 EST Date: Mon, 27 Oct 97 15:48:41 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710272048.AA12781@MOGLI.rutgers.edu> To: alap@winlab.rutgers.edu Subject: Re: Exam Problem Cc: crose@MOGLI.rutgers.edu Status: RO Nope, not yet. I think at this point I'll just add the score on this to the score on your next aexam... no time right now.. Cheers, Chris Rose From crose Mon Oct 27 23:49:32 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA13340; Mon, 27 Oct 97 23:47:12 EST Date: Mon, 27 Oct 97 23:47:12 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710280447.AA13340@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: class on tuesday Status: RO Hi Folks, There is a serious chance that I'll have to cancel class on tuesday (10/28/97). I'll send email as early as possible (probably in the early PM). I'll be at the maternity hospital (in NY) and will laptop-email from there if at all possible. 501 STUDENTS: About the test: it is commulative (covers EVERYTHING from the begnning of the term until what we've done so far and maybe a little more besides). However, it will be heavily skewed towward the systems stuff we've been doing of late with a fair amount of physical modeling and solutions. Don't worry TOO much about the Lagrangian. Anything I give you on that will be heavily guided. But you'll need to know all about linearization, laplace transforms transfer functions (that was tomorrow's lecture among other things) and everything else we've done so far. 543 STUDENTS: Everything up through and including chapter 6 is fair game. I won't have your solutions ready (probably) for the answers some of you handed in via email, but will return them with your graded quiz II at the latest. You should know all about switching and sorting and packet networks etc. I'll also almost certainly spring some probability on you! But I will carefully guide you this time. EVERYONE: if we miss tomorrow we'll have to make up the class. The only day which seems feasible is on a friday late afternoon. We'll cross that bridge (schedule a class) when we come to it if necessary. It's also possible that I might try to give you a web lecture (but don't count on it because I dont' think the technology is quite there yet.... CHEERS ALL! Chris Rose From jasonjen@ece.rutgers.edu Tue Oct 28 00:55:34 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA13473; Tue, 28 Oct 97 00:55:34 EST Received: from localhost (jasonjen@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) with SMTP id XAA13241 for ; Mon, 27 Oct 1997 23:51:31 -0500 Date: Mon, 27 Oct 1997 23:51:30 -0500 (EST) From: Jason Jen To: Chris Rose Subject: homework solution? Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Dr. Rose, Hi, will the homework solutions be posted sometime this week? Thanks, Jason J a s o n J e n ------------------------------ Electrical Engineering Office: EE 214 Tel: (732) 445-5385 ------------------------------ From coslit@ece.rutgers.edu Tue Oct 28 13:10:24 1997 Return-Path: Received: from ece.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA13998; Tue, 28 Oct 97 13:09:19 EST Received: (from coslit@localhost) by ece.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.6) id MAA10153; Tue, 28 Oct 1997 12:05:11 -0500 Date: Tue, 28 Oct 1997 12:05:11 -0500 From: Dianne Coslit Message-Id: <199710281705.MAA10153@ece.rutgers.edu> To: 330_543@mogli.rutgers.edu, 330_501@mogli.rutgers.edu Status: RO CLASSES ARE CANCELLED FOR TONIGHT. D. COSLIT ECE From crose@localhost.localdomain Tue Oct 28 23:55:32 1997 Return-Path: Received: from localhost.localdomain (ppp-11.ts-3.nyc.idt.net) by MOGLI.rutgers.edu (4.1/25-eef) id AA14540; Tue, 28 Oct 97 23:55:08 EST Received: (from crose@localhost) by localhost.localdomain (8.8.5/8.8.5) id MAA00683; Tue, 28 Oct 1997 12:39:47 -0500 Date: Tue, 28 Oct 1997 12:39:47 -0500 From: Christopher Rose Message-Id: <199710281739.MAA00683@localhost.localdomain> To: 330_501@mogli.rutgers.edu, 330_543@mogli.rutgers.edu Subject: class cancelled for tuesday 10/28 Cc: crose@MOGLI.rutgers.edu Status: RO Hi FOlks, Class is cancelled tonite. Baby seems to be making an entrance. Will contact 501 folks tonite or tomorrow about exam on thursday and further details. We'll need to reschedule class ... probably for a friday later in the term. Cheers, Chris Rose From crose Tue Oct 28 23:57:42 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA14561; Tue, 28 Oct 97 23:57:41 EST Date: Tue, 28 Oct 97 23:57:41 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710290457.AA14561@MOGLI.rutgers.edu> To: jasonjen@ece.rutgers.edu Subject: Re: homework solution? Cc: crose@MOGLI.rutgers.edu Status: RO yes, they will.. Cheers From crose Wed Oct 29 00:22:38 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA14649; Wed, 29 Oct 97 00:21:18 EST Date: Wed, 29 Oct 97 00:21:18 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710290521.AA14649@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: Baby Cc: crose@MOGLI.rutgers.edu Status: RO Hi FOlks, Our baby boy was born today at about 4:40 pm. Mother and baby are resting comfortably. Thanks for your forebearance (sorry I had to miss class). FOr 501 folks, exam is still on for thursday. FOr 543 solks, I'll see if we can get the solutions posted to the PS's by this weekend at the latest (friday is what I mean). Gotta go now... I'm almost asleep as you can probably tell my my typing. Cheers, Chris ROse From zwf@winlab.rutgers.edu Tue Oct 28 23:23:04 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA00351; Tue, 28 Oct 97 23:22:36 EST Received: from dilbert.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id UAA24756; Wed, 29 Oct 1997 20:23:01 -0500 Received: from winlab.rutgers.edu by dilbert.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id UAA01264; Wed, 29 Oct 1997 20:23:00 -0500 Sender: zwf@winlab.rutgers.edu Message-Id: <3457E172.555649F0@winlab.rutgers.edu> Date: Wed, 29 Oct 1997 20:22:58 -0500 From: Wenfeng Zhang X-Mailer: Mozilla 4.03 [en] (X11; I; SunOS 5.6 sun4u) Mime-Version: 1.0 To: "330_543@MOGLI" <330_543@MOGLI> Subject: TA announcement Content-Type: multipart/alternative; boundary="------------B3409D54AA002EB2F04BCB73" Status: RO --------------B3409D54AA002EB2F04BCB73 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hello, This is TA announcement. As the midterm exam for 330:543 is coming, some of you may want to discuss with me about what you learned. I change my office hour of next Tuesday to Monday morning. Only for next week! If you want to meet with me at that time, you are highly desirable to mail me in advance with your problems. Your cooperation will save time of all of us. My email is zwf@winlab.rutgers.edu See you on next Monday. Regards, Wenfeng -- Wenfeng Zhang Post: BPO 23888, PO BOX 1119, Piscataway, NJ 08855 Phone: (908)463-1964 (H) http://www.eden.rutgers.edu/~wfzhang --------------B3409D54AA002EB2F04BCB73 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Hello,

This is TA announcement.
As the midterm exam for 330:543 is coming, some of you may want to discuss with me about what you learned.  I change my office hour of next Tuesday to Monday morning. Only for next week!  If you want to meet with me at that time, you are highly desirable to mail me in advance with your problems. Your cooperation will save time of all of us.
My email is zwf@winlab.rutgers.edu
See you on next Monday.

Regards,
Wenfeng 

-- 
Wenfeng Zhang
Post: BPO 23888, PO BOX 1119, Piscataway, NJ 08855
Phone: (908)463-1964 (H)
http://www.eden.rutgers.edu/~wfzhang
  --------------B3409D54AA002EB2F04BCB73-- From crose Wed Oct 29 03:15:37 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00687; Wed, 29 Oct 97 03:15:36 EST Date: Wed, 29 Oct 97 03:15:36 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710290815.AA00687@MOGLI.rutgers.edu> To: xuyang@rutcor.rutgers.edu Subject: Re: 2nd midterm Cc: crose@MOGLI.rutgers.edu Status: RO Thanks Yang! I'll figure something out. WHat I think we'll do if possible is to start you at 3pm somewhere and then we'll migrate over to SEC117 for the second half. I'll get back to you wth details soon. However, if for some reason we've not connected by Sunday, please email me a reminder. At worst you can sit in my lab for the first half. Cheers, Chris Rose From crose Wed Oct 29 03:15:37 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00687; Wed, 29 Oct 97 03:15:36 EST Date: Wed, 29 Oct 97 03:15:36 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710290815.AA00687@MOGLI.rutgers.edu> To: xuyang@rutcor.rutgers.edu Subject: Re: 2nd midterm Cc: crose@MOGLI.rutgers.edu Status: RO Thanks Yang! I'll figure something out. WHat I think we'll do if possible is to start you at 3pm somewhere and then we'll migrate over to SEC117 for the second half. I'll get back to you wth details soon. However, if for some reason we've not connected by Sunday, please email me a reminder. At worst you can sit in my lab for the first half. Cheers, Chris Rose From crose Wed Oct 29 04:07:42 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA00864; Wed, 29 Oct 97 04:06:05 EST Date: Wed, 29 Oct 97 04:06:05 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710290906.AA00864@MOGLI.rutgers.edu> To: 330_501, 330_543 Subject: mail problems Cc: crose@MOGLI.rutgers.edu Status: RO hi Folks, I've been having some mailer problems which may have sent some confusing mail. 1) there is NO CLASS for 330_543 on this coming thursday. The exam is on tuesday and I'll have solutions to the last two PS out on the web by friday (actually Wenfeng is working on this now). 2) there is NO CLASS for 330_501 on tuesday next. Thanks for all the well wishes on the new baby. Steph and I really appreciate it. Cheers, Chris Rose From shahid@er3.rutgers.edu Wed Oct 29 12:55:22 1997 Return-Path: Received: from er3.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA01753; Wed, 29 Oct 97 12:55:21 EST Received: from localhost (shahid@localhost) by er3.rutgers.edu (8.8.5/8.8.5) with SMTP id JAA26813; Thu, 30 Oct 1997 09:55:37 -0500 (EST) Date: Thu, 30 Oct 1997 09:55:37 -0500 (EST) From: Shahid Kagal To: crose@ece.rutgers.edu Cc: crose@MOGLI.rutgers.edu Subject: Some problems in Chap 4 Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Respected Prof. Rose, Following are some problems faced in Chap. 4: 1. Page 96 : For compact superconcentrators there is a case discussed when each second stage superconcentrator has more than one output.How do we deduce that there is more than one row at the output of second stage. 2. Prove that the banyan network is the mirror image of the inverse banyan network : Sir, I have a real problem flipping the network. 3.Many to one concentration page 103-104 : Second portion of assigning for each active input i an output Oi in order to satisfy the monotone condition. In that how is the boundary for the interval decided, i.e. Oi = [ Sum over i'< i (ni'), Sum over i'<=i (ni'-1) ] 4. Are we suppose to prepare the Pippenger network. Thank You, Shahid. From crose Wed Oct 29 14:31:35 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA01857; Wed, 29 Oct 97 14:29:45 EST Date: Wed, 29 Oct 97 14:29:45 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710291929.AA01857@MOGLI.rutgers.edu> To: shahid@eden.rutgers.edu Subject: Re: Some problems in Chap 4 Cc: 330_543 Status: RO Hi Shahid, Thanks for the questions. I'm reposting them to the group for comment. Anybody care to take a crack at Shahid's questions. let's get a discussion going so I know you're alive out there :) Cheers Chrs Rose ***************** Following are some problems faced in Chap. 4: 1. Page 96 : For compact superconcentrators there is a case discussed when each second stage superconcentrator has more than one output.How do we deduce that there is more than one row at the output of second stage. 2. Prove that the banyan network is the mirror image of the inverse banyan network : Sir, I have a real problem flipping the network. 3.Many to one concentration page 103-104 : Second portion of assigning for each active input i an output Oi in order to satisfy the monotone condition. In that how is the boundary for the interval decided, i.e. Oi = [ Sum over i'< i (ni'), Sum over i'<=i (ni'-1) ] 4. Are we suppose to prepare the Pippenger network. From crose Wed Oct 29 14:33:05 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA01860; Wed, 29 Oct 97 14:31:23 EST Date: Wed, 29 Oct 97 14:31:23 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710291931.AA01860@MOGLI.rutgers.edu> To: shahid@eden.rutgers.edu Subject: Re: Some problems in Chap 4 Cc: 330_543 Status: RO Oh and yes I'd like yoyu to know about the Pippinger network. We need to know just abot everything up through and including chapter 6. I'll exclude the appendix to chapter 6 which is amore of a culture piece than course material. Cheers Chris Rose From zwf@winlab.rutgers.edu Wed Oct 29 14:39:09 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA01873; Wed, 29 Oct 97 14:37:34 EST Received: from gsm.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id LAA01277; Thu, 30 Oct 1997 11:37:52 -0500 Received: from winlab.rutgers.edu by gsm.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id LAA24513; Thu, 30 Oct 1997 11:37:34 -0500 Sender: zwf@winlab.rutgers.edu Message-Id: <3458B7CC.C8C8C1FA@winlab.rutgers.edu> Date: Thu, 30 Oct 1997 11:37:32 -0500 From: Wenfeng Zhang X-Mailer: Mozilla 4.03 [en] (X11; I; SunOS 5.5.1 sun4u) Mime-Version: 1.0 To: "330_543@MOGLI" <330_543@MOGLI> Subject: Solution for Chapter 6 Content-Type: multipart/alternative; boundary="------------40A15F97CE14DDF5418B1317" Status: RO --------------40A15F97CE14DDF5418B1317 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, everybody The copies of the problem solution for chapter 6 will be available after 4:30PM. You can come to my office (EE 218) and get them. I will put the copies in a box near the door. The solution covers all of the problems after Chapter 6. Sorry for that I am too busy to give you a PS version on the net by next Tuesday. Further, I just find I cannot access the solution for any previous chapters from the homepage of 330:543. I donot know whether you suffer the same thing. To give you a quick reference, I will make a mirror site for all the solutions on my homepage. It is available soon via http://www.eden.rutgers.edu/~wfzhang Regards, Wenfeng -- Wenfeng Zhang Post: BPO 23888, PO BOX 1119, Piscataway, NJ 08855 Phone: (908)463-1964 (H) http://www.eden.rutgers.edu/~wfzhang --------------40A15F97CE14DDF5418B1317 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, everybody

The copies of the problem solution for chapter 6 will be available after 4:30PM. You can come to my office
(EE 218) and get them.  I will put the copies in a box near the door. The solution covers all of the problems after Chapter 6.   Sorry for that I am too busy to give you a PS version on the net by next Tuesday.

Further, I just find I cannot access the solution for any previous chapters from the homepage of 330:543. I donot know whether you suffer the same thing.  To give you a quick reference, I will make a mirror site for all the solutions on my homepage.  It is available soon via http://www.eden.rutgers.edu/~wfzhang
Regards,
Wenfeng 

-- 
Wenfeng Zhang
Post: BPO 23888, PO BOX 1119, Piscataway, NJ 08855
Phone: (908)463-1964 (H)
http://www.eden.rutgers.edu/~wfzhang
  --------------40A15F97CE14DDF5418B1317-- From crose Wed Oct 29 14:42:57 1997 Return-Path: Received: by MOGLI.rutgers.edu (4.1/25-eef) id AA01888; Wed, 29 Oct 97 14:41:16 EST Date: Wed, 29 Oct 97 14:41:16 EST From: Christopher Rose Full-Name: Christopher Rose Message-Id: <9710291941.AA01888@MOGLI.rutgers.edu> To: 330_543, zwf@winlab.rutgers.edu Subject: Re: Solution for Chapter 6 Status: RO WAY TO GO WENFENG!!!!!!! I'll check out the ece problems. it's NOTORIOUSLY FLAKY. I've been having mailer problems as well. From minfan@paul.rutgers.edu Thu Oct 30 13:07:19 1997 Return-Path: Received: from paul.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA01292; Thu, 30 Oct 97 13:07:04 EST Received: from localhost (minfan@localhost) by paul.rutgers.edu (8.8.5/8.8.5) with SMTP id KAA12034; Fri, 31 Oct 1997 10:07:12 -0500 (EST) Date: Fri, 31 Oct 1997 10:07:12 -0500 (EST) From: Min Fan To: Christopher Rose Cc: shahid@eden.rutgers.edu, 330_543@MOGLI.rutgers.edu Subject: What will be covered in the midterm II In-Reply-To: <9710291929.AA01857@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO We did not go through chapter 6. Will we be tested on chapter 6? Thanks. ------------------------------------------------ Min Fan Office : Hill 355 Tel:(732)445-3213 ext. 20 Email: minfan@paul.rutgers.edu ------------------------------------------------ From shahid@er5.rutgers.edu Thu Oct 30 16:00:07 1997 Return-Path: Received: from er5.rutgers.edu by MOGLI.rutgers.edu (4.1/25-eef) id AA01467; Thu, 30 Oct 97 16:00:07 EST Received: from localhost (shahid@localhost) by er5.rutgers.edu (8.8.5/8.8.5) with SMTP id NAA12051 for ; Fri, 31 Oct 1997 13:00:11 -0500 (EST) Date: Fri, 31 Oct 1997 13:00:09 -0500 (EST) From: Shahid Kagal To: Christopher Rose Subject: Re: Some problems in Chap 4 In-Reply-To: <9710291929.AA01857@MOGLI.rutgers.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Respected Prof. Rose, I think I haven't got any answers from our team. Shall I post the questions once again or wait for sometime. Yours, Shahid. From alap@winlab.rutgers.edu Thu Oct 30 23:21:58 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA01818; Thu, 30 Oct 97 23:21:46 EST Received: from gsm.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id UAA19484; Fri, 31 Oct 1997 20:21:50 -0500 Received: by gsm.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id UAA29824; Fri, 31 Oct 1997 20:21:50 -0500 Date: Fri, 31 Oct 1997 20:21:50 -0500 From: alap@winlab.rutgers.edu (Ana Lucia Pinheiro) Message-Id: <199711010121.UAA29824@gsm.winlab.rutgers.edu> To: 330_543@mogli Subject: Re: Some Problems in Chapter 4 Status: RO Shahid - 1. Page 96 : For compact superconcentrators there is a case discussed when each second stage superconcentrator has more than one output.How do we deduce that there is more than one row at the output of second stage. 2. Prove that the banyan network is the mirror image of the inverse banyan network : Sir, I have a real problem flipping the network. ------- 1. I believe this is up to you, I mean, it depends what kind of switchings you have available to use. 2. to see that banyan is the mirror of inverse banyan, just pick the inverse banyan and change input and output. You will see you got the banyan. I think this is what the book means by "mirror". I hope it helps (and I hope it's right :) ) -Ana. From alap@winlab.rutgers.edu Fri Oct 31 00:50:47 1997 Return-Path: Received: from liman (liman.rutgers.edu) by MOGLI.rutgers.edu (4.1/25-eef) id AA01949; Fri, 31 Oct 97 00:50:34 EST Received: from gsm.winlab.rutgers.edu by liman (SMI-8.6/SMI-SVR4) id VAA19679; Fri, 31 Oct 1997 21:50:37 -0500 Received: by gsm.winlab.rutgers.edu (SMI-8.6/SMI-SVR4) id VAA29882; Fri, 31 Oct 1997 21:50:37 -0500 Date: Fri, 31 Oct 1997 21:50:37 -0500 From: alap@winlab.rutgers.edu (Ana Lucia Pinheiro) Message-Id: <199711010250.VAA29882@gsm.winlab.rutgers.edu> To: 330_543@mogli Subject: Re: Some Problems in Ch. 4 Status: RO Shahid 3.Many to one concentration page 103-